Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
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).
