I think this is possible and it doesn’t require AI. It only requires a certain kind of “infectious Turing machine” described below.
Following Gwern’s comment, let’s consider first the easier problem of writing a program on a small portion of a Turing machine’s tape, which draws a large smiley face on the rest of the tape. This is easy even with the *worst case* initialization of the rest of the tape. Whereas our problem is not solvable in worst case, as pointed out by Richard_Kennaway.
What makes our problem harder is errors caused by the random environment. We could model these errors by spontaneous random changes in the letters written on the Turing machine’s tape. But it’s easy to make a computation robust to such errors: A naive way to do it is to repeat each square 100 times and assign a repair bot to repeatedly scan the 100 squares, compute majority, and convert the minority squares back to the majority letter. This is not so different from how your laptop repeatedly scans its memory to prevent errors.
Now we get to what I think is the hard part of the problem: How to organize a random environment into squares of Turing machine tape? I don’t know how to do it in Conway’s Life, but I would guess it’s possible. An interesting question is whether *any* cellular automaton that supports a Turing machine can also support an infectious Turing machine. Again I would guess yes.
Does an infectious Turning machine require AI? There is certainly something lifelike about a device that gradually converts its environment into squares of its own tape. The tape squares reproduce, but they hardly need to be intelligent.
But okay, we’re setting the bar low by competing against a *random* environment. As Oscar_Cunningham points out, a random environment is unlikely to produce anything smart. If we set the bar higher by asking the infection to compete against an environment containing life or intelligence, then it might need to be significantly smarter in order to take over the rest.
I think this is possible and it doesn’t require AI. It only requires a certain kind of “infectious Turing machine” described below.
Following Gwern’s comment, let’s consider first the easier problem of writing a program on a small portion of a Turing machine’s tape, which draws a large smiley face on the rest of the tape. This is easy even with the *worst case* initialization of the rest of the tape. Whereas our problem is not solvable in worst case, as pointed out by Richard_Kennaway.
What makes our problem harder is errors caused by the random environment. We could model these errors by spontaneous random changes in the letters written on the Turing machine’s tape. But it’s easy to make a computation robust to such errors: A naive way to do it is to repeat each square 100 times and assign a repair bot to repeatedly scan the 100 squares, compute majority, and convert the minority squares back to the majority letter. This is not so different from how your laptop repeatedly scans its memory to prevent errors.
Now we get to what I think is the hard part of the problem: How to organize a random environment into squares of Turing machine tape? I don’t know how to do it in Conway’s Life, but I would guess it’s possible. An interesting question is whether *any* cellular automaton that supports a Turing machine can also support an infectious Turing machine. Again I would guess yes.
Does an infectious Turning machine require AI? There is certainly something lifelike about a device that gradually converts its environment into squares of its own tape. The tape squares reproduce, but they hardly need to be intelligent.
But okay, we’re setting the bar low by competing against a *random* environment. As Oscar_Cunningham points out, a random environment is unlikely to produce anything smart. If we set the bar higher by asking the infection to compete against an environment containing life or intelligence, then it might need to be significantly smarter in order to take over the rest.