The Busy Beaver Challenge

bbchallenge.org

write C(n,m) for (10)^n A0 1^m then we get the rules: 1. C(n,m) -> halt, if n+m odd 2. C(n,m) -> C(((n+m)/2)+1,n+1), if n+m even We start in C(0,0) and C(n,n) -> C(n+1,n+1) for all n, so the machine is infinite and visits C(n,n) for all n but ((n+m)/2)+1-(n+1) = (n+m-2n)/2 = -(n-m)/2 so the TM divides the difference of the exponents by 2 until the difference becomes odd. Then it halts. This can only go on forever if the difference is 0 to begin with. So C(n,m) -> halt, if n!=m no regular language can seperate C(n,n) and C(n,m) for n!=m