It's easy enough to build Turing Machines that don't halt. But how complex can we make these? For example, suppose a machine has access to its state transition table and can write to it like a C program could point to its own code page in RAM and poke around. The motivation for the question should clear up the particulars:
Imagine that we've build an intelligent (but deterministic) autonomous robot that can completely self-repair from the environment. Imagine that it's a space probe. We don't want it to shut itself off. Because it can change itself physically, it can also change its own programming. We have no control over that once we launch the thing. It's within the realm of possibility it will go through a series of changes that result in it halting and becoming space junk.
Is there any way to understand the topology of a self-modification "trajectory" so that we could minimize the risk of halting? For example, maybe there's some kind of "attractor" where halting is rare.
Or do we just have to assume that Chaitin's Omega constant applies, and there's an unknown constant probability that the thing will halt?
Update: Thanks for the comments--they sent me in new directions. Here is some additional background.
- Microsoft has an active research project along these lines.
Turing proved that, in general, proving program termination is undecidable. However, this result does not preclude the existence of future program-termination proof tools that work 99.9 percent of the time on programs written by humans. This is the sort of tool that were aiming to make. --Byron Cook, the project leader
- Usually we want programs to halt and give us some output. But for the example I gave, we want it to run forever. Can we build an AI that won't spontaneously turn itself off with high probability, like Shannon's "Ultimate Machine"? Supposing that a civilization is effectively computable (a big if, but somewhere to start), is there any way to guard against self-halting? Peter Suber studied this idea, limited to legislative systems, and created the game Nomic. Paul Krugman gives an example of a government that actually did self-halt. My own thoughts about this are in this paper, where I assumed Chaitin's Omega would "tax" survival probability of any computable system. This is not very satisfying, however. It implies that we can't do any better than randomly selecting an algorithm.