Halting Undecidability proof faulty?

[Pyrotex]

And you are just an extremely dishonest, passive aggressive snivevling little weasel. This has ABSOLUTELY NOTHING TO DO WITH ANYTHING I SAID.

As usual you are responding to some ridiculous imaginary argument that was never stated by anyone.

Did you not say this:

...That being said there is pretty good reason to believe that such an infinite regress really would occur. Any halting machine run on itself would at some point try to trace at least a part of its own computations - at which point it would redo everything it had done up to that point when it would again restart and so forth. Each time it would be tracing an additional level of depth.

Well, it turns out that the phrases I underlined above, basically are the definition of "Infinite Recursion". Recursion is a software term describing the event where a program or subroutine calls itself. Where there are no internal tests or conditions specifically coded to end the recursion, the parent could end up calling itself without limit -- "infinite regress" or "infinite recursion".

 

So it DID have something to do with what you said.

 

On the other hand, you were correct about me being a passive aggressive sniveling little weasel. :shrug:

 

OH! You misspelled "sniveling".

[Kriminal99]

kriminal, you're acting very disrespectfully toward others on this board. it is not necessary to insult someone if you think their post is not relevant to the discussion.

i read through this whole topic again to try to understand what in particular you object to about turing's proof.

 

 

 

this seems to be the guts of your problem. but this needn't be the case. many machines are capable of running their own machine code as input, and halting. so why would the halting machine be any different?

 

as i stated in the other thread, H(H'(H(x,i))) should be able to run just as well as H(x,i), if H(x,i) is actually constructable. however, as my prime algorithm demonstrates, such an algorithm is not.

 

It isn't just that it is a turing machine, it is the exact design of the overall machine that copies the input and then runs the halting algorithm on it.

 

The halting algorithm traces the input machine's behavior. The fact that it requires the input of the input machine proves this.

 

The larger machine copies input and then runs the halting alogrithm on it - call it D.

 

So what happens when you run it on itself?

 

Say X is the machine code of D, so the input was originally [X]

The first part of D copies the input, so the input is changed to [XX]

This is then fed to the halting algorithm. The halting algorithm at some point traces the actions of the machine represented by X on input X. The represented machine happens to be D.

 

So in tracing, it again copies the X, then gives it to the halting machine portion of X.

 

So the resulting tape contains [XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX... forever]

 

This is a unique problem that only occurs with the setup of copying input and then giving it to a machine that traces. It isn't the halting machine that is different, it is the complete setup that is implied in the halting proof.

 

Though it is often expicitly stated that the overall setup has the copying preprocessor, it is necessarily implied in the diagonolization proof by having the Halting machine "run on itself" when you have only given it a single machine encoding.

 

This is undeniable logical proof that this setup results in a unique type of unending program that would not occur when trying to solve the halting problem for any normal type of program.

 

 

In other words, the proof is a sham - it assumed nonsense as a premise by creating such a convaluted setup.

[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]

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, 19622.

 

 

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.