What are the limits of non-halting?

Question

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.

Answer 1

Your question is about many things, but let me give an answer focused on just one interesting issue, the question of determining how long a program will run.

The busy beaver function exactly measures how long programs of a given size run before halting (among the ones that do halt). There are versions of the busy beaver function for any notion of computation, but let us consider the case of C programs, since you mentioned them. Note that for any natural number $n$, there are an enormous number of C programs of size $n$, measured in kilobytes, say. Nevertheless, this enormous number is finite. Among all programs of size at most $n$, some halt and some do not. Define $b(n)$ to be the running time in clock cycles of the longest-running but halting C program of size at most $n$.

The interesting thing is that the busy beaver function is not computable! If we had a way of computing $b$, then we would be able to solve the halting problem, since given any C program, we look at its size $n$, compute $b(n)$ and run the program for that many steps; it it hasn't halted by then, we know it will never halt. Another way to say this is that if we have an oracle black-box that allows us somehow to compute the function $b$, then we would be able to answer any halting problem query. Since it is impossible to solve the halting problem, it follows that we cannot compute the busy beaver function.

Edit. In your update, you mention the problem of solving the halting problem 99.99% of the time. The general problem of solving almost all instances of a problem, as opposed to all instances of a problem, gives rise to the subject known as generic case complexity. In particular, the black-hole phenomenon occurs when the difficulty of an unsolvable or infeasible problem is concentrated in a very tiny region, outside of which it is easy. It is not good, for example, to base an encryption scheme on a problem whose difficulty has high worst-case complexity, but whose average-case complexitty is low, for if the robbers can rob the bank 10% of the time, it is good enough for them.

In fact, Alexei Miasnikov and I proved that the halting problem itself admits a black hole---for some of the standard computation models, there is a method to solve the halting problem with probability $1$, using the natural asymptotic density measure on the space of programs. I explain further details in this MO answer.

Answer 2

Total functional programming allows considerable freedom to program with a guarantee of termination. You don't get unbounded loops but you can still use structural recursion.

Such a computer would be connected to the outside world via sensors. If we allow guarded recursion then we get a nice framework for writing algorithms to process the data that can guarantee that from time to time, the robot will produce an output, rather than disappear into its own thoughts.

I don't know if this answers your question, but it seems to fit. Such a machine wouldn't poke its own state transition table, but it would be able to "program itself" by making use of higher order functions to build new functions.