1

Regarding the busy beaver function, what's a simple rule to prove that the machine runs forever in one direction? I believe there's something about the machine not backtracking far enough before it repeats a state?

As an example, prove that this machine doesn't halt, where $A$ is the initial state, and the machine starts with an all-$0$ tape:

     A   B   C
   ------------
0 | 1RB 1LA 1LB
1 | 1RA 0RC   H

Obviously I'm looking for as general a rule as possible.

r.e.s.
  • 14,371
Frucifer
  • 11
  • Have you tried to prove anything about that Turing Machine? (Obviously we are hoping you to have done as much work as possible.) – Rob Arthan Sep 12 '15 at 01:05
  • I edited your question to make the transition table unambiguous. Hopefully I picked the interpretation you intended. – r.e.s. Sep 12 '15 at 01:35
  • @r.e.s: you are very kind. Don't you think the OP should do some work? – Rob Arthan Sep 12 '15 at 01:57
  • Thanks for the formatting. Not sure exactly what you're looking for, but I have done some "work" so far. I've got a program that reduces the pool of candidates to 6 for N=2 and 1044 for N=3, but there are still a lot of machines that just run off in one direction in a very simple pattern. That's what I'm trying to eliminate now. – Frucifer Sep 12 '15 at 13:28

1 Answers1

0

The technique I was thinking of is explained here:

http://www.cogsci.rpi.edu/~heuveb/research/BB/status/nonhalters/simpleloop.html

Frucifer
  • 11