Are turing machines with an infinite program tape that is completely random, or another example is a Game of Life simulation on an infinite randomly initialized grid, still turing machines, so to speak?

edit: if this is the wrong place to ask this(?) remove it

  • 4
    $\begingroup$ This is the correct place to ask this, but you might want to be a bit more focused and formal about the specific question you want. Currently it borders being opinion-based, since it is not really well-defined what "equivalent to TM with infinite sized random memory" means. I took the interpretation of the question to ask only about TMs. $\endgroup$
    – nir shahar
    Jan 23, 2022 at 23:23

1 Answer 1


They are still turing complete. Here is some intuition for why:

You can manually "clear", say, the first $100$ positions by replacing them with a blank. Then, we can "split" the tape into two parts by writing a special character $\#$, for which the first half are all of the tape contents before the first occurrence of $\#$ and the rest of the tape is everything else.

We can now consider the first part of the tape to be a "cleaned out" tape, like a usual TM would have. When we run out of space, we move $\#$ a few cells forward (any constant number you really want) and set the memory it the area it was before to $\sqcup$ (effectively allocating a constant extra memory and then clearing the contents out).


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.