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](http://research.microsoft.com/en-us/um/cambridge/projects/terminator/) 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](http://www.youtube.com/watch?v=cZ34RDn34Ws)"? 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](http://www.nomic.net/~nomicwiki/index.php/GameOfNomic). Paul Krugman gives an [example](http://www.nytimes.com/2010/02/08/opinion/08krugman.html?em) of a government that actually did self-halt. My own thoughts about this are in [this paper](http://arxiv.org/abs/0812.0644), 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.



What are the limits of non-halting?
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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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](https://mathoverflow.net/questions/10358/solving-np-problems-in-usually-polynomial-time/10379#10379). 


