Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

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.
share|improve this question
1  
Obviously, a Universal Turing Machine has the maximal halting problem of all Turing machines... –  François G. Dorais May 30 '10 at 21:18
2  
I wish the programs I run would shut themselves off sometimes. –  Andrej Bauer May 31 '10 at 4:59

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
    
Thanks--your response made me think about aspects that hadn't occurred to me. I'm not sure how BB helps in this case though. In this case we get to design the robot's programming from the ground up. So we can make it halt easily enough, or make it loop forever easily. So the theoretical limitations on functions over general machines don't prevent us from designing particular ones with halting/not built in. E.g. given size N and run time M, we can build a machine to specs in some but not all cases. Is there theory that limits what we can design, rather than limiting what we can discover? –  Stanislav May 31 '10 at 2:08
    
The 'black hole' idea is exactly the kind of thing I was hoping for. Thanks! –  Stanislav Jun 1 '10 at 14:58
    
For the black hole in the halting problem, see J. D. Hamkins and A. Miasnikov, The halting problem is decidable on a set of asymptotic probability one, Notre Dame J. Formal Logic 47, 2006. arxiv.org/abs/math/0504351. –  Joel David Hamkins Jun 1 '10 at 18:43

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.

share|improve this answer
    
This sounds like a very practical approach (limiting what Herr Robot can do), but it won't work once it becomes smart enough to re-engineeer its own construction, will it? A different analogy is this: suppose a government runs on axioms (ha!) for its legislative processes, starting with a constitution. The constitution permits self-modification in order to meet unforseen challenges. Are there constitutions that are guaranteed (or likely) not to 'halt'? This would be a state in which no more legislation is possible. (Such halting has actually happened at least once!) –  Stanislav May 31 '10 at 1:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.