Halting Undecidability proof faulty?

[Pyrotex]

Originally Posted by Kriminal99

The only part of that the proof does not explicitly state is the part about tracing the computations. So we are left to wonder how on earth the Halting Machine would operate without tracing the input machine.
But that is irrelevant....

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?

[Kriminal99]

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

Originally Posted by phillip1882

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]

Originally Posted by Pyrotex

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]

Originally Posted by alexander

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]

Originally Posted by Pyrotex

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?

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]

Originally Posted by Kriminal99

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]

Originally Posted by Kriminal99

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

Originally Posted by CraigD

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]

Originally Posted by Pyrotex

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]

Originally Posted by Kriminal99

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.

Originally Posted by Kriminal99

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.