Halting Undecidability proof faulty?

[Pyrotex]

Originally Posted by CraigD

I came to this conclusion for several reasons...
I know what a person with a Bachelor of Science degree in Math, a long career as a professional programme...
a fairly reliable ability to judge when someone is claiming to know a subject they do not...

I concur.

Infinite recursion is not involved in the Turing Halting Problem.
In fact, a casual inspection reveals that it can't involve recursion at all.
A (hypothetical) algorithm capable of concluding that some arbitrary program will never halt, could NOT do so by actually running or simulating that program.

[Clue] Because the program would never halt.

[Kriminal99]

Originally Posted by CraigD

I came to this conclusion for several reasons

• First, because of your low reputation at hypography, and history here of making bizarre claims and being argumentative
• Next, because you claim that a very well-known proof, which absolutely every professional and academic computer scientist of my acquaintance accepts, is wrong.
• Last, because you are unwilling of unable to complete a Turing-machine-writing exercise such as I would include as a homework assignment or test question in an undergraduate computer science class, to test a student’s understanding of the subject. If a student did not complete this exercise, I would assume he didn’t understand the subject, so, as you have not, I conclude the same thing

I don’t consider my conclusion “brilliant”, but routine. Stating the obvious, I believe you’re being sarcastic, Krim, an rhetorical technique I believe you’ll find ineffective here at hypograph. I know what a person with a Batchelor of Science degree in Math, a long career as a professional programmer, years of participation in internet forums, and the ability to research, self-educate, and attend professional training and academic classes, knows. One of the skills common among people with my background is a fairly reliable ability to judge when someone is claiming to know a subject they do not, which I believe, you, Krim, are doing in this thread.

I am glad you have taken it upon yourself to declare reputations for other people based on your ignorant interpretation of their behavior. If anyone has a rep here, it is you for repeated use of debate fallacies and missapling information from sources like wikipedia for the purpose of adhering to some naive bastardized interpretation of the scientific method.

Computer scientists are not epistemologists, yet deal with topics governed by the rules of epistemology. Some of those rules have been adapted into other disciplines, and some of them have been forgotten. Scientists often make claims that violate the rules of epistemology, and the more obvious ones get called out even if they do not strictly violate the rules of mathematics or the scientific method. The more difficult applications of epistemology slip by.

I DONT CARE WHAT YOU THINK I SHOULD OR SHOULD NOT DO. YOU REPEATEDLY DEMONSTRATE IGNORANCE IN YOUR DEALINGS WITH OPPOSING ARGUMENTS.

[Kriminal99]

Originally Posted by Pyrotex

I concur.

Infinite recursion is not involved in the Turing Halting Problem.
In fact, a casual inspection reveals that it can't involve recursion at all.
A (hypothetical) algorithm capable of concluding that some arbitrary program will never halt, could NOT do so by actually running or simulating that program.

[Clue] Because the program would never halt.

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.

[Kriminal99]

Originally Posted by Pyrotex

phillip,
you know, sometimes we just have to accept that some proofs are over our heads, and trust that if the Nobel laureates and acknowledged math wizards of the world say "it's so", then they're prolly right.

I find Turing's "halting problem" to be just barely within the boundary of my ability to understand.

However, Goedel's "incompleteness theorem" is just a smidge outside the boundary. No matter how much I tackle it, and from what direction, there is a point where my brain just goes "ppffftftftphhhhht".

One of the reasons I switched from Physics to Computer Science in graduate school was that I could not understand the derivation (or the proper use) of the Green's Function.

Many are called. Few are chosen.

This is called appeal to authority fallacy. If those people know what they are talking about because of their nobel prizes or whatever else, then they should be able to provide a convincing argument.

A proof can be wrong even if the thing it is claiming is true. Rather than present a ridiculous proof containing logic errors, they should just present the program phillip presented as proof which cause people to believe the claim immediately instead of remaining partially or fully skeptical.

My god you don't get the incompleteness theorem?!?!

[modest]

Originally Posted by Kriminal99

I am glad you have taken it upon yourself to declare reputations for other people based on your ignorant interpretation of their behavior.

By "low reputation at Hypography" CraigD is referring to the reputation feature which is part of the vBulletin software with which this forum is run. Your reputation is displayed under your avatar next to your post. It reflects the amount of positive and negative feedback you have received by your peers on this forum.

~modest

[phillip1882]

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.

IE if there exists a halting machine H that always loops if run on itself but otherwise works, the halting problem is still possibly decidable except for halting machines. Which is very likely a trivial distinction from the idea that the halting problem is possibly solvable.

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.

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.

[Pyrotex]

Originally Posted by Kriminal99

...If those people know what they are talking about because of their Nobel prizes or whatever else, then they should be able to provide a convincing argument.

But they DID provide a convincing argument. That is not to say that everyone will be able to understand it. Case in point, you?

Specifically, Turing provided a totally solid and convincing argument for his theory, by demonstrating the validity for the general case of ANY arbitrary algorithm.

A proof can be wrong even if the thing it is claiming is true. Rather than present a ridiculous proof containing logic errors, they should just present the program phillip presented as proof...

phillip provided only one arbitrary program. A differently constructed Halting Algorithm might easily decide the haltability of phillip's program, but not of some other. If we followed your suggestion, we would have to provide a "proof-program" for every conceivable Halting Algorithm.

Turing's proof contained no logic errors. Your attempts so far to demonstrate otherwise have either relied upon assumptions of how a particular Halting Algorithm should work (in your opinion), or were based on very flimsy reasoning.

My god you don't get the incompleteness theorem?!?!

And you do?

AMOF, I do "get" the incompleteness theorem. I understand how it was proven and I understand the meaning of it, and how it pertains to logic in general. So far, I have not been able to follow a few crucial steps of the mathematics at the core of the proof.

[modest]

While the following link doesn't present a full proof, it did help me understand how the proof works. I didn't get it 'till I read this very short description. If anyone else (like myself) is having trouble wading through this thread, it might help.

What computers can't do

~modest

[Pyrotex]

Originally Posted by Kriminal99

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.

OH! You misspelled "sniveling".

[Kriminal99]

Originally Posted by phillip1882

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.