I'm a CS undergrad so forgive me if this question isn't formulated well. I got curious about the Busy Beaver function recently, and it got me wondering how all the n-state Turing machines are kept track of.

Is there like a list of all of the machines, along with whether they halt or not? Or is there some other way?

  • $\begingroup$ I think wikipedia has the (short) list of all known busy beavers. And the highest number of states there is, unsurprisingly, low. $\endgroup$
    – rus9384
    Commented Feb 17 at 10:22
  • $\begingroup$ @rus9384 but that is not my question. The Busy Beaver is the machine that achieves the maximum number of ones. But what I want to know is how do you keep track of all the n-state TMs so that you could evaluate which ones halt (and don't). $\endgroup$
    – Slim Shady
    Commented Feb 17 at 10:30
  • $\begingroup$ I suppose they prove which machines do not halt and show for how long the rest of machines run. Which is in general impossible, but if a machine has too few states to encode the halting problem in it, it is possible. $\endgroup$
    – rus9384
    Commented Feb 17 at 10:32
  • $\begingroup$ @rus9384 okay but how do you deal with trillions of TMs, like when n=4? $\endgroup$
    – Slim Shady
    Commented Feb 17 at 10:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.