The halting problem

I've read very little myself, and have always wondered why everyone was so obsessed with the general case. It just feels "unheard of" to consider anything but the general case, even though practically we would never need it.

Last edited on

chrisname (7395)

Because it's theoretical computer science, it's not going to refer to specific cases. It's like saying "Why don't the laws of classical mechanics refer to a red ball instead of just 'any object'?"

Last edited on

My alteration isn't going from "any object" to "red ball", it's going from "any object" to "any object that can exist in our universe".

Last edited on

Last time I checked, code can't change while you look at it - you should always be able to know the behavior of a program by examining it.

Sure it can. Machines where code and data exist on the same memory space permit self-modifying code. As a counter-example for your second definition of h(), imagine a p that compiles, loads, and executes i. What if i contains an implementation of h() and a call to h'(p, i)?

It's not unheard of. There are such things as termination proofs. You can take a specific program and attempt to prove that it terminates (or not) for all inputs. The theorem merely states that there exist programs that terminate, and which you are unable to prove that they do. The general case is interesting because, for example, it proves that there exist no perfect size-optimizing compilers. It's also interesting how the theorem is related to Gödel's theorems.

It is a decidable problem if instead of Turing machines, you defined it for finitely bound computers. Which is what we are using now for all practical purposes. It's not solvable for Turing machines, which can use unbounded amount of memory and time and therefor can have an unbounded amount of states.

I remember once someone posted, as a joke, a job request for basically a program that solves the halting problem, with the intention of showing how ridiculous the contract programers are that they will all jump on and promise to build you an impossible program. In reality, this was not an impossible program to make, in terms of real life computers.

Last edited on

helios wrote:
Sure it can. Machines where code and data exist on the same memory space permit self-modifying code. As a counter-example for your second definition of h(), imagine a p that compiles, loads, and executes i. What if i contains an implementation of h() and a call to h'(p, i)?

The implementation of h is the human reading the code while it is not running. Don't tell me you're considering mind-reading devices connected to the computer?

@htirwin I remember that

The implementation of h is the human reading the code while it is not running. Don't tell me you're considering mind-reading devices connected to the computer?

I'm not sure what you mean. If h is computable then whether it's computed in hardware or wetware is irrelevant.

Duthomhas (13112)

In reality, this was not an impossible program to make, in terms of real life computers.

Yes it is. Boundedness has nothing to do with the halting problem.

Even if you give someone a specific program, if it is sufficiently complex you cannot solve the halting problem.

A lot of the problem depends on how you define things, too. For example, does the following program terminate?

#include <iostream>

int main()
{
  std::cout << "Hello world!\n";
}

The C++ Standard tries to guarantee that it will, in fact, halt, because the program is allowed to continue to termination after simply submitting the text to the output device.

But the OS may never finish executing the program. Or refuse to return control to it until the text actually has printed on the console. The problem with this restriction is that it unreasonably adds extra variables into the execution of the program. So, we discard those possibilities. We assume that the OS is a good doggie and always returns to play.

Therefore, we'll consider this an example where the halting problem can be solved.

Now take the code to Minecraft. Does it halt? Write an algorithm that proves it will. (Without crashing, mind you.) Even if the OS and network and everything else that works with it behave perfectly, and discounting radioactive decay and things like the sun exploding, it it is possible that program can never terminate. Isn't it?

Now, write a program that proves that Minecraft will terminate at some point. You can't. Not even for that one specific program.

That's the halting problem.

Hope this helps.

Yes it is. Boundedness has nothing to do with the halting problem.

I think I may have been wrong about this example. I got the idea from here, but I may have misunderstood something. Certainly if you know the specs of the machine it is meant to run on, you can decide it. Or if you are given an upper bound on how much memory it can use.
http://en.wikipedia.org/wiki/Halting_problem#Common_pitfalls

I am pretty sure you can write a program to determine if Minecraft will halt on a specific input.

It is hard to think how to translate what the halting problem means in terms of real computers because it is formalized with Turing machines. I am pretty sure, that given a Turing machine, it is decidable to decide if it accepts a string. But building a decider that can decide wether an arbitrary machine accepts an arbitrary string is not decidable.

http://cs.stackexchange.com/questions/27779/rices-theorem-vs-turing-completeness/27783#comment53933_27783

Last edited on

Computergeek01 (5613)

Sorry to interrupt here, but I've always wondered about this thought experiment and specifically about this part: "... given a program ...". Does this mean we are given a black-box to analyse externally? Or does this say that we are given the 'code', as in we know what the required conditions for the termination would be? Because this makes all the difference in the world in my mind. The input is already known, so if we are able to track a variable during execution and analyse whether it is trending toward or away from the conditions for termination, then we can absolutely predict if a program will close. But if we aren't given the code then this problem is as useless as all of you trying to guess what the person physically nearest to me is wearing right now. You simply aren't given enough information to establish an answer. The input is 'me' and the black box is the person nearest to me.

A Turing machine can be made to perform any algorithm, including simulating other Turing machines, and running code.

They formalize the problem by making the program that is give as input a Turing machine, and the decider, or program that decides if the program it is given as input terminates, also a Turing machine.

The decider is given an encoding of the Turing machine, which is essentially equivalent to being given the code, and really, also the code of the operating system and any other software it depends on in any way?

The proof that halt is not decidable is something like this,

bool haltsp(p){
    return halts(P,P) ? true : false;
}

void nhp(P){
    if ( haltsp(P) ) {
        while(1);
    }
    else {
        return;
    }
}

//the contradiction comes from calling 
nhp(nhp);
//if nhp halts on input nhp, then nhp loops on nhp
//if nhp doesn't halt on input nhp, then nhp halts on nhp

Last edited on

Or if you are given an upper bound on how much memory it can use.

A non-halting program doesn't necessarily need infinite memory.

"... given a program ...". Does this mean we are given a black-box to analyse externally? Or does this say that we are given the 'code', as in we know what the required conditions for the termination would be?

Yes, that last one.

The input is already known, so if we are able to track a variable during execution and analyse whether it is trending toward or away from the conditions for termination, then we can absolutely predict if a program will close.

Some termination proofs for individual loops involve proving that
1. The loop terminates when f(S) <= 0, S being the program state and f being some arbitrary function.
2. f(S) is strictly monotonically descending at every step of the loop.
Meeting both conditions is enough to say that the loop terminates, but some loops that terminate don't meet them. For example, see the Collatz conjecture.

A non-halting program doesn't necessarily need infinite memory.

Right, but with finite memory, you have finitely many states. When processing the input, if it will not return, then it must repeat a sequence of states over and over in which case you can detect that it will not halt. It's similar to the difference between rational and irrational numbers.

The only way you cannot detect that the program will not halt is if it is diverging, which means it is transitioning infinitely to new states in no real pattern. But this is only possible with unbounded memory.

Last edited on

When processing the input, if it will not return, then it must repeat a sequence of states over and over in which case you can detect that it will not halt. It's similar to the difference between rational and irrational numbers.

Right. Now, how long do you let it run to be sure that it's repeating states? For a computer capable of passing through a trillion states per second, 6 ints is enough to last 1.9e+38 years.

The only way you cannot detect that the program will not halt is if it is diverging, which means it is transitioning infinitely to new states in no real pattern. But this is only possible with unbounded memory.

How long do you wait until you decide that the memory usage is unbounded?

Last edited on

How long do you wait until you decide that the memory usage is unbounded?

You have to know in advance how much memory the program is allowed to use. If it exceeds that upper bound, assuming the program doesn't crash, it would then necessarily fall into that cyclical pattern on the machine that it is expected to run it.

In really it would probably either crash, or go on forever corrupting memory etc. So I'm not sure what to make of that. In the theory, they use idealized models.

According to mainstream CS theory though, HALT is decidable if you are given a specific memory limitation. I think to really make this work in real life, you would need to be given both the program along with the exact specifications of the machine that will run it, and all other software that would be running, and the input would include every single event and variable on the entire system, and the exact timing of the events, or really, just the entire state of the machine.

Last edited on

What happens when you allow for access to external sensors for true RNG?

What happens when you allow for access to external sensors for true RNG?

That counts as part of the input.