Halting Undecidability proof faulty?

[phillip1882]

so, what your saying is, just because the universal halting machine can't run on itself, doesn't mean that it's not universal? i would disagree. if the halting algorithm when run on itself goes into an infinite loop, then its not very universal , as it can't accept itself as input. this is the guts of what alan turing is saying. he didn't say you couldn't make a halting algorithm for some problems, he said you can't make one that solves all problems.

[Pyrotex]

Hi, I've mentioned this a couple times before, but it bears repeating.
There is NOTHING in the proof for the Undecidability of the Halting Problem that says that the Halting program has to run on itself, or that it must simulate or emulate the execution of the copy of itself, or that it must mess around with recursion, or for that matter, ANY other technique.

The Halting Problem is more inclusive than that. It doesn't CARE what technique or algorithm or trick is used to determine that some arbitrary program will or will not halt, The method is NEVER declared.

This is what makes the proof work!!!! You just assume that your program WORKS. You don't CARE how it does it. Then, assuming your program works, you follow the logic and confront a contradiction.
The contradiction means your assumption was wrong.

All these arguments here about how the program "has" to work, just muddy the water and confuse the issue.

[phillip1882]

hmm, not entirely sure i agree pyrotex, alan turing is assuming that the halting machine is capable of running on itself as input, though a slightly altered version of itself, then goes on to prove that this leads to a contradiction. that is, can't you can't construct a halting machine capable of accepting altered halt, which is a ligament algorithm.

[Pyrotex]

The Halting Program takes any other program as an input.
Nothing is ever said about what is DONE with that input.
Maybe it just counts the number of IF statements and divides by the number of Comments, and this magically tells it whether or not the other program will halt.

If you feed the Halting Program (HP) a copy of itself (hp), the HP doesn't know that hp is a copy of itself and doesn't care. It just counts IFs and Comments like it always does and comes up with an answer.
It still works.

But now you modify hp to make hp'. hp' is adjusted so that if hp would have halted, hp' doesn't; if hp would have gone on forever, hp' halts.

Now when HP is given hp' as an input, HP gives the wrong answer!

Ta-da!

[phillip1882]

"But now you modify hp to make hp'. hp' is adjusted so that if hp would have halted, hp' doesn't; if hp would have gone on forever, hp' halts."

a bit of an inaccurate description, hp always halts, it just it returns doesn't halt. (i think i made the same mistake in my description in the other post.)
this may seem nit picky, but it's an important distinction, because, hp when run on hp' input shouldn't have a problem, as far as whether it halts.

let's say hp algorithm is this, if "if" statements - comments <1 then return doesn't halt. else "if" - comments >=1, return halt. clearly this algorithm is a bad one, but it just for demonstration.
now create h'. h' will have the following algorithm. if "if" statements -comments <1 return halt. "if" - comments >=1 go into infinite loop. what will h return when run on h'? it reads that it has two if statements, and no comments. so it would go into first if statement, return doesn't halt. clearly however h' does halt in this case. if you add two comments to h' code, then h will see that, and return halt. but clearly h' doesn't halt in this case. in short, as you said pryotex, h will always return the wrong answer when run on h'.

[Pyrotex]

I guess the only recourse is to go read the original Turing Proof, or a good "wikipedia" version of it.

[CraigD]

Originally Posted by Pyrotex

I guess the only recourse is to go read the original Turing Proof, or a good "wikipedia" version of it.

Or read my recent humble presentation of the subject, “A short description of Turing machines and a halting problem undecidability proof”.

I’ve seen many excellent description of Turing machines, and of Turing’s halting problem undecidability proof, but can’t recall any that combine the two, and are text-based, rather than graphical (sketches), so decided to write my own.

Graphical presentations, while arguably easier to follow, can, I think lead to some confusion about the basic “mechanics” of Turing machines.

This webpage, which I linked to in post #8, is one of may good graphical summary of the proof I’ve seen.