# Are turing machines & equivalents with infinite sized random programs still turing machines?

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

• 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. Jan 23, 2022 at 23:23

## 1 Answer

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).