Halting Undecidability proof faulty?

[k99]

There appears to be a clear problem with these proofs.

 

A halting machine attempting to operate upon itself would cease it's normal function and simply always loop.

 

A function which gives 0 if the input function is defined would cease it's normal function and always loop if operated upon itself.

 

The simple reasoning for this is either of these actions would cause an infinite regress whereas normally an infinite regress of this type would not occur...

 

So these two functions could work fine on everything else, but then if they were operated on themselves they would not work.

 

Every Halting problem undecidability proof asks us to assume that such functions could operate on themselves.

[Mr Skeptic]

That is true. However, even if the only type of program that the halting machine can't figure out is a program that it is part of, that does show that a universal halting machine cannot be made. Basically, you can't calculate everything because, for example, you can't calculate yourself.

[bascule]

A halting machine attempting to operate upon itself would cease it's normal function and simply always loop.

 

You seem to be missing the metalinguistic abstraction that's going on here.

 

An algorithm which theoretically solves the halting problem won't infinitely recurse when fed itself as its own input. In the above example you are feeding the algorithm its own implementation as both the algorithm and the argument. In Lisp terms you'd be feeding the algorithm its own S-expression for itself.

 

However, it's an S-expression. It needn't be evaluated. This is the "code is data" idea from Lisp, that programs themselves can be represented as S-expressions. You seem to be assuming that the algorithm will get caught in a loop of infinitely recursing as it evaluates itself, however it won't ever evaluate itself as it should only analyze the S-expressions, not actually evaluate them.

 

In the above example, your program should halt and return that its own code will halt when fed itself, as any algorithm which theoretically solves the halting problem should always halt.

[k99]

That is true. However, even if the only type of program that the halting machine can't figure out is a program that it is part of, that does show that a universal halting machine cannot be made. Basically, you can't calculate everything because, for example, you can't calculate yourself.

 

Yes. But then all that has been proven is that the Halting Problem is undecidable for T, but may be decidable for T - {H}. But this proof has been sold as the idea that it is impossible in general to make a machine/algorithm that tells when another machine/algorithm will halt/accept.

 

You seem to be missing the metalinguistic abstraction that's going on here.

 

An algorithm which theoretically solves the halting problem won't infinitely recurse when fed itself as its own input. In the above example you are feeding the algorithm its own implementation as both the algorithm and the argument. In Lisp terms you'd be feeding the algorithm its own S-expression for itself.

 

However, it's an S-expression. It needn't be evaluated. This is the "code is data" idea from Lisp, that programs themselves can be represented as S-expressions. You seem to be assuming that the algorithm will get caught in a loop of infinitely recursing as it evaluates itself, however it won't ever evaluate itself as it should only analyze the S-expressions, not actually evaluate them.

 

In the above example, your program should halt and return that its own code will halt when fed itself, as any algorithm which theoretically solves the halting problem should always halt.

 

 

Well you seem to realize in the setup given by the proof that if it did happen to trace computations, an infinite recursion could occur as it copied and traced over and over again. You simply are claiming that you don't think it is going to trace. This is an assumption since it is not proven... and honestly not a very strong one. As the form of the Halting proof is a proof by contradiction, this assumption could be the cause of the contradiction.

 

Your final statement is a similar claim to what the above poster said, IE we simply assume that the halting machine can operate on itself. This limits the result of the proof to saying that there is no halting machine that can retain it's normal function in this setup. There could still be a halting machine that works fine in other cases.

 

I don't fool around with silly programs like Lisp/Prolog, but the situation there is the same as any version of the proof. A succesful universal algorithm (can operate on others) very well may need to trace part of the computation of the input algorithm to come to a conlcusion. This idea that it is only data that it recieves is a bit silly, because if it is designed to take algorithm encodingns as data then it knows exactly how to turn that data back into an algorithm. Any such (that traced computatitons) universal algorithm in the setup the proof provides would infinintely recurse.

Edited November 23, 2008 by k99
multiple post merged

[bascule]

Well you seem to realize in the setup given by the proof that if it did happen to trace computations, an infinite recursion could occur as it copied and traced over and over again. You simply are claiming that you don't think it is going to trace.

 

No, I'm saying if you have a naive algorithm which contains something which can be thrown into an infinite loop, you don't have a valid solution.

 

Any potential solution to the halting problem should ALWAYS halt itself. Otherwise it's invalid.

 

Your final statement is a similar claim to what the above poster said, IE we simply assume that the halting machine can operate on itself.

 

Any solution to the halting problem should be able to operate on ANY algorithm, including itself.

 

I don't fool around with silly programs like Lisp/Prolog

 

I'd strongly suggest you re-evaluate your opinion of Lisp, and I think it'd help greatly in understanding these sorts of problems.

 

A succesful universal algorithm (can operate on others) very well may need to trace part of the computation of the input algorithm to come to a conlcusion.

 

If your idea of "tracing" is execution, then you must be careful that such action can't throw your algorithm into an infinite loop, otherwise your algorithm won't be a valid solution.

 

It's possible to execute code which recurses infinitely without the code doing the execution suspending infinitely itself. For example, I work in a functional language with several concurrent processes, all of which are executing infinite loops. However, this doesn't hang the scheduler, as the scheduler allows for a finite number of "reductions" (think calls to other functions) before suspending a given process and moving on to the next one.

 

Any solution to the Halting problem which actually evaluates the code in question would need to incorporate some sort of similar mechanism to prevent an infinite recursion.

[k99]

No, I'm saying if you have a naive algorithm which contains something which can be thrown into an infinite loop, you don't have a valid solution.

 

Any potential solution to the halting problem should ALWAYS halt itself. Otherwise it's invalid.

 

 

 

Any solution to the halting problem should be able to operate on ANY algorithm, including itself.

 

 

 

I'd strongly suggest you re-evaluate your opinion of Lisp, and I think it'd help greatly in understanding these sorts of problems.

 

 

 

If your idea of "tracing" is execution, then you must be careful that such action can't throw your algorithm into an infinite loop, otherwise your algorithm won't be a valid solution.

 

It's possible to execute code which recurses infinitely without the code doing the execution suspending infinitely itself. For example, I work in a functional language with several concurrent processes, all of which are executing infinite loops. However, this doesn't hang the scheduler, as the scheduler allows for a finite number of "reductions" (think calls to other functions) before suspending a given process and moving on to the next one.

 

Any solution to the Halting problem which actually evaluates the code in question would need to incorporate some sort of similar mechanism to prevent an infinite recursion.

 

I am not sure what your knowledge regarding this subject is, but what we were conversing about was the fact that a universal touring machine operated on itself often attempts to trace it's own computations. Combine this with a preprocessor that copies input, and give the composite machine it's own encoding and you have an infinite regress.

 

So you are repeatedly referring to this trivial notion that the halting machine is supposed to be able to operate on itself in the setup the "proof" provides. This doesn't do or mean anything signifigant. You could make halting algorithms and machines all day long and they just wouldn't be able to operate on themselves. This scenario is not what the halting proof is aiming for. The author wants to be able to say that the halting problem is undecidable the power set of Touring Machines, or just undecidable period.

 

Because the entire purpose of a Halting Machine would be to ask the question "What does Machine M do with input R", tracing computations can be considered to be part of it's definition (although it may not be possible to prove this using the language of mathematics)

 

If a Halting Machine traces computations by definition, Touring's proof is utterly trivial and says nothing about the ability to create halting algorithms in general.

 

The scheduler you mentioned is not an algorithm that can tell if the code is going to halt, because it would use inductive reasoning instead of deductive reasoning. IE it runs it, watches what happens, and then could record the results if it chose to. This is a different subject.

 

The halting problem involves deductively reasoning based on the form of the code to see if it is going to halt or not. It can use things that look like inductive reasoning, only if it can also be represented with deductive reasoning (like mathematical induction). This is why the scheduler is not a counterexample to the halting problem. It solves the "Does the machine halt by the kth transition problem" And then guesses that if it doesn't it probably won't halt at all.

 

There is no proof that an algorithm cannot exist to solve the halting problem - only that the algorithm couldn't function on itself in the setup Touring created for his "proof".

[bascule]

I am not sure what your knowledge regarding this subject is

 

Well, let's just say I'm familiar with several types of combinator calculus and the Chomsky Hierarchy. I'm also reading the Annotated Turing, which is an excellent book.

 

but what we were conversing about was the fact that a universal touring machine operated on itself often attempts to trace it's own computations.

 

1) It's a "Turing machine"

2) In what context are you using "trace"? Perhaps you mean "evaluate"? Trace has a number of specific meanings in this context, particularly in the theory of compilers.

 

Combine this with a preprocessor that copies input, and give the composite machine it's own encoding and you have an infinite regress.

 

Again, I'm not sure what vernacular you're using so I keep defaulting back to Lisp. Are you trying to say you wish to pass an algorithm the S-expression if itself as its own argument, i.e. you want to feed the algorithm its own source code? (provided it was able to operate on it)

 

So you are repeatedly referring to this trivial notion that the halting machine is supposed to be able to operate on itself in the setup the "proof" provides.

 

Yes, because that's terribly important. Any algorithm which solves the Halting Problem should be universal. It should work on any algorithm, including itself.

 

This doesn't do or mean anything signifigant. You could make halting algorithms and machines all day long and they just wouldn't be able to operate on themselves.

 

Yes, and such algorithms couldn't satisfy the halting problem, because they're not universal.

 

This scenario is not what the halting proof is aiming for. The author wants to be able to say that the halting problem is undecidable the power set of Touring Machines, or just undecidable period.

 

Yes, within the scope of the Chomsky Hierarchy the algorithm should work for algorithms expressed in the entire set of recursively enumerable languages. This would, of course, include any halting decidability algorithms themselves. After all, they are algorithms. Otherwise, your solution isn't universal.

 

Because the entire purpose of a Halting Machine would be to ask the question "What does Machine M do with input R", tracing computations can be considered to be part of it's definition (although it may not be possible to prove this using the language of mathematics)

 

There is no need for a halting algorithm to explicitly evaluate anything, but even if it does, if it recurses infinitely by doing so the algorithm is faulty because then there are sets of inputs which do not produce an answer. Any algorithm attempting to solve the halting problem that infinitely recurses is broken.

 

Any solution to the halting problem must itself halt for ANY input, including itself. Otherwise it's not a solution.

 

If a Halting Machine traces computations by definition

 

A halting decidability algorithm doesn't need to evaluate anything by definition. You should read about static analysis.

 

There's a whole world of opportunities available to you using only static analysis and transformation of code. For example, the compilers for most languages are able to transform code from one language to another without ever executing it. There are wonderful tools for picking apart code, such as IDA.

 

I'm out of gas for now on the rest of your comments, but feel free to respond...