Halting Undecidability proof faulty?

[Kriminal99]

Moderation note: this and the following post were moved from the 18973, because they are about Turing’s proof being inaccurate or bogus, not writing a specific program to determine if a program halts

 

yeah so basically all you ever need to do if you really get someone stubbornly claiming that the halting problem is not accurate is to write a while loop that tests the condition of an unsolved problem. the twin prime is one of my favourites, but you could do the riemann hypothesis as well.

 

The problem is that the halting proof REALLY IS innaccurate which is why everyone claims that it is.

 

In fact i have seen this happen alot in various scientific disciplines - when the same thing can be proven through some other means, some historical figure comes up with an problematic proof to support it. Then no one challenges the proof, because it is a moot point anyways. It's the same thing with the monty hall problem. It is really annoying for extremely logical minded people though to whom everything makes perfect sense and works in perfect harmony until they get into the harder disciplines and find that there is a bunch of nonsensical bs randomly distributed througout the material that is beleived only because it shares conclusions wiht a much stronger argument.

[Kriminal99]

Hi, guys.

I'm sorry to interrupt, but it may be possible that you have overlooked something.

 

According to Wikipedia, "...the halting problem is a decision problem which can be stated as follows: given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input.

 

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines."

 

So, if you choose one particular algorithm, say finding the next prime number, and use that alone -- you have NOT proven that the halting problem is bogus, or that Turing was wrong, or that the whole thing is "full of errors".

 

What Turing asked was, (1) Is there an Algorithm, A(i,x), that has two inputs;

 

(2) The first input, i, is a description (or the code itself) of any arbitrary program;

 

(3) The second input is a finite value, x;

 

(4) Can the algorithm A(i,x) decide whether or not the program, i, will halt or not, if you feed the input, x, into the program, i?

 

Turing proved that the existence of such an Algorithm, A(i,x), capable of doing this for ANY ARBITRARY PROGRAM, i, AND ARBITRARY VALUE, x, was impossible.

 

....

 

So if it's impossible in the general case, then it should be impossible in at least one case, which is what phillip has shown.

 

Turing's proof is bogus. There is no such thing as a proof that you never have to doubt to begin with, and a so called proof that takes that form is especially suspect. A bunch of people who wouldn't even know the difference if it made epistemological sense or not agreeing that it's a proof is irrelevant. He makes an assumption that is obviously false during his construction of his proof.

[Kriminal99]

I can certainly provide an example.

 

Euclid's Parallel postulate states, well rather Playfair's rendition of that postulate states that at most one line can be drawn through any point not on a given line parallel to the given line in a plane. It is and remains an axiom, however the further mathematicians looked at space, and the fact that it is not always, or nearly ever is it flat, that concept had to be changed later, when looking at non-flat spaces, and planes that bend and curve, the geometry that made many current physics theories possible that axiom had to be changed to accommodate a new way at looking at things, where the Euclidean postulate still holds true for it's range, a postulate stating that more than one line that can be extended through any given point parallel to another line of which that point is not part, is one of the fundamental postulates in non-euclidean geometry (i.e. elliptic curve and hyperbolic geometries).

 

This is an example of how something once thought to be true, while still being true, had to be changed to suit a different theory of looking at things.

 

By the way, both postulates hold true, it just depends on which perspective you look from...

 

But this doesn't reperesent some kind of duality of existence which is what academics would seem to have us believe to avoid pointing to some "celebrated" proof and saying that it is wrong or inappliccable. It's just different models that we defined based on what was useful for a given application.

 

In that case there is no reason to get rid of one model or the other because they both have their uses. The thing I have a problem with is when something that is claimed in the past is inapplicable AND inaccurate and yet we hold on to it to avoid pointing to some "celebrated" result and saying that it was actually wrong.

 

There is no place for politics in the quest for knowledge, and this kind of thing introduces chaos.

[Kriminal99]

No. It is ENTIRELY relevant.

 

It demonstrates that YOU do not understand how a Halting Algorithm would operate.

 

Say, Krim? Don't they make medications now for Compulsive Defiance Syndrome? :friday:

 

What on earth do you think you are talking about. In order for the proof to fail, it doesn't even need to fully trace the computations. It just needs to begin to try and see what the simulated machine will do.

 

Even though every halting algorithm that works for less than general cases actually does simulate the input machine's behavior to some degree in a way that would cause a unique non-functioning infinite loop if put into the setup Turing proposes in his proof, I allowed at first for the possibility that it might not be absolutely necessary for a Halting Machine to do this.

 

What I since realized is that the small amount of simulation required to create this unique function preventing infinite loop is what a Halting Machine (if not UTM) does by DEFINITION when the input of the simulated machine is also required.

 

A UTM in general could just look at the beginning states of an input machine to determine something about it, but if it needed the input the simulated machine would recieve then by definition it would be tracing the computations to the degree I am suggesting.

[CraigD]

But this doesn't reperesent some kind of duality of existence which is what academics would seem to have us believe to avoid pointing to some "celebrated" proof and saying that it is wrong or inappliccable.

Krim, no person with a working understanding of the halting problem, professional academic or not, considers Turing’s proof of its undecidability to “represent some kind of duality of existence”, nor considers this proof any more or less valid because it’s “celebrated”.

 

The problem I have with your objections to this proof is that you don’t appear to understand computation theory in general nor the halting problem in particular well enough for me to take you seriously. Were you to demonstrate that you have even a minimal understanding of this subject by completing the introductory exercise I provided in post #33, I’d take you more seriously.

 

It’s not necessary to having a working knowledge of the subject to have some understanding of the halting problem, but to understand it well enough to criticize a formal proof concerning it, it is.

[Pyrotex]

...In order for the proof to fail, it doesn't even need to fully trace the computations. It just needs to begin to try and see what the simulated machine will do.

 

Even though every halting algorithm that works for less than general cases actually does simulate the input machine's behavior to some degree in a way that would cause a unique non-functioning infinite loop if put into the setup Turing proposes in his proof, I allowed at first for the possibility that it might not be absolutely necessary for a Halting Machine to do this. ...

I have tried my best to follow your logic, but despite 35 years of programming experience, more years of experience in rhetoric and presentational logic than you have been alive, and familarity with the Halting Problem (and "Undecidable" propositions in general), I cannot trace what YOU consider to be a "proof" that Turing was wrong.

 

Too much of your text is dependent on "...it will likely...", "...it will tend to...", "...it probably won't..." and similar lapses in logic.

Point of example, your quote above: "In order for the proof to fail, it doesn't even need to fully trace the computations".

 

What do you mean by "In order for the proof to fail"?

The simplest explanation for that (that I can think of) is:

 

The assumed program P, which contains a subroutine H that can:

- accept as input a text or numeric representation of an arbitrary program A;

- and can, in a finite amount of time, return a value that says either:

- - program A will indeed halt; or

- - program A will never halt;

is actually possible.

 

Though P may not exist now, it certainly could be written. And fed any arbitrary program, even a copy of itself, P will correctly determine whether or not it will halt, and will determine this in a finite time. In other words, P will always halt. Even if fed a program A that never halts.

 

Is THIS what you mean by "In order for the proof to fail"?

[Kriminal99]

Krim, no person with a working understanding of the halting problem, professional academic or not, considers Turing’s proof of its undecidability to “represent some kind of duality of existence”, nor considers this proof any more or less valid because it’s “celebrated”.

 

The problem I have with your objections to this proof is that you don’t appear to understand computation theory in general nor the halting problem in particular well enough for me to take you seriously. Were you to demonstrate that you have even a minimal understanding of this subject by completing the introductory exercise I provided in post #33, I’d take you more seriously.

 

It’s not necessary to having a working knowledge of the subject to have some understanding of the halting problem, but to understand it well enough to criticize a formal proof concerning it, it is.

 

Ok I'll try something different for a change. HOW EXACTLY did you come to the brilliant conclusion that I "don't appear to understand computation theory in general"? If you could answer that question, you wouldn't need to make such a ridiculous blanket claim.

 

But to be honest I don't care what you know of my understanding. What do you know? Obviously not enough to directly deal with anything I have to say.

[Kriminal99]

I have tried my best to follow your logic, but despite 35 years of programming experience, more years of experience in rhetoric and presentational logic than you have been alive, and familarity with the Halting Problem (and "Undecidable" propositions in general), I cannot trace what YOU consider to be a "proof" that Turing was wrong.

 

Too much of your text is dependent on "...it will likely...", "...it will tend to...", "...it probably won't..." and similar lapses in logic.

Point of example, your quote above: "In order for the proof to fail, it doesn't even need to fully trace the computations".

 

What do you mean by "In order for the proof to fail"?

The simplest explanation for that (that I can think of) is:

 

The assumed program P, which contains a subroutine H that can:

- accept as input a text or numeric representation of an arbitrary program A;

- and can, in a finite amount of time, return a value that says either:

- - program A will indeed halt; or

- - program A will never halt;

is actually possible.

 

Though P may not exist now, it certainly could be written. And fed any arbitrary program, even a copy of itself, P will correctly determine whether or not it will halt, and will determine this in a finite time. In other words, P will always halt. Even if fed a program A that never halts.

 

Is THIS what you mean by "In order for the proof to fail"?

 

Here, complete formalization:

 

Define S as a class of Universal Turing Machines, that takes an encoding of another Turing machine and an it's input. It computes a function that cannot be computed by another Universal Turing machine that only takes a TM encoding and not the input it runs on.

 

Class G is a Universal Turing Machine that takes an encoding of an element of S, copies it, and then runs it on itself. Class G is a proper subset of Class S, and therefore can take itself as input.

 

Any instance of G(G) will recurse infinitely for a unique reason that precludes any other function. This is necessitated by the fact that G (which is a subset of S) computes a function that requires the information of what the input encoding will do with it's input. It will keep copying the input over and over again.

 

The halting proof presents an instance of G(G) but also says that this instance of G(G) will calculate the halting function. This is a falsehood which is responsible for the ultimate contradiction Turing derives in his proof.

[CraigD]

HOW EXACTLY did you come to the brilliant conclusion that I "don't appear to understand computation theory in general"?

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.

What do you know?

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.

[Pyrotex]

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. :confused:

[Kriminal99]

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]

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. :confused:

 

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]

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. :confused:

 

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]

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]

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