Halting Problem

[Kriminal99]

1. Touring machines are incremental

 

2. Therefore the first step in deciding what a given machine does with a given input is to find out what is the first thing it does with that input. You can look at it's number of states etc but that does not get you anywhere towards deciding what it does with the input.

 

3. The machine created in every halting undecidability proof version trivially causes an infinite loop that trivially and uniquely causes the Halting machine's function to fail. The halting machine asks what a halting machine would do with itself as input, to which the answer is to ask the question what a halting machine would do with itself as input... and this would continue forever.

 

4. For the majority of algorithms, it is possible to decide the halting problem. For the one's that the best you can do is to trace the algorithm as far as we know, it still does not have the same problem outlined in the proof. If a trace never halts, then the program never halts, if a trace halts then the program halts.

 

5. This does not disprove halting undecidability for the class of all Universal Touring machines. However it shows the proof only shows that the Halting problem is undecidable for a halting machine + self copy input generator and NOTHING ELSE.

 

The best reason for generalizing the result to other machines is that the proof machine construction (halting machine + self copy input generator or "What does this algorithm do with itself as input" algorithm) might be hidden inside any other touring machine machine. However no one would intentionally create such a machine for non theoretical purposes. Why would you create an algorithm that evaluates any algorithm with itself as input?

 

Also although it is supposed to be hard to recognize such an algorithm inside another potential input (rice's theorem) with 100% accuracy there are ways to do it with less (but not bad) accuracy.

[phillip1882]

kriminal, let's take an example halting algoritm and show why it fails.

 

def Halt:

for all inequalities, test if they are increasing or decreasing.

if increasing or stay the same over a period of time, return doesn't halt. if decreasing, return halt.

 

this seems like a fairly good algortim that would work in a majority of cases. now i will write anti halt.

 

def antiHalt:

for all inequalites test if they are increasing or decreasing.

if increasing or stay the same over a period of time, return halt. if decreasing, go into infinite loop.

 

now what would Halt return when run on anti Halt which is run on an abstract algorithm?

halt would test the inequalites of anti halt, and every time give the wrong answer. this is turings point. you cannot unviversally decide whether any algorithm will halt or not. you can certianly write halting algorithms for specific algorithms, but there is no halting algorithm that will work in every case.

[IDMclean]

halt would test the inequalites of anti halt, and every time give the wrong answer and this is Turings point. you cannot universally decide whether any algorithm will halt or not. you can certianly write halting algorithms for specific algorithms, but there is no halting algorithm that will work in every case.

Turing's proof and Turing's point is only valid in Aristotelian logic. It arises from the non-contradiction principle. We can accept his result if and only if we accept Aristotelian logic as universal; however, if we reject Aristotelian logic and the noncontradiction principle as well as the principle of explosion, Turing's result does not necessarily hold universally. Paola Zizzi makes a point of this in her paper "Turning the Liar paradox into a metatheorem of Basic logic". The problem Zizzi stirs up is what replaces the decision problem in such a logic? Her logic is necessarily generally undecidable in the classical sense.

[Kriminal99]

kriminal, let's take an example halting algoritm and show why it fails.

 

def Halt:

for all inequalities, test if they are increasing or decreasing.

if increasing or stay the same over a period of time, return doesn't halt. if decreasing, return halt.

 

this seems like a fairly good algortim that would work in a majority of cases. now i will write anti halt.

 

def antiHalt:

for all inequalites test if they are increasing or decreasing.

if increasing or stay the same over a period of time, return halt. if decreasing, go into infinite loop.

 

now what would Halt return when run on anti Halt which is run on an abstract algorithm?

halt would test the inequalites of anti halt, and every time give the wrong answer. this is turings point. you cannot unviversally decide whether any algorithm will halt or not. you can certianly write halting algorithms for specific algorithms, but there is no halting algorithm that will work in every case.

 

By the way that particular construction doesn't work for what you were trying to do. Halt would simply accurately detect that antiHalt was not halting. The input for anti halt is irrelevant, since the input for Halt is the composed machine not the original input of AntiHalt. Funny that someone + rep for that lol.

 

The real proof is more complicated than that and depends on a machine infinitely generating input for itself. If you were trying to make sense of the wiki article on the subject (There is a lot of obfuscation used to hide that the proof is poorly reasoned), you might have seen something like this:

 

h(i,j) = 1 if i halts on j, 0 if i does not halt on j

 

g(i) = 1 if h(i,i) = 0, loop forever if h(i,i) = 1

 

(Note that three obfuscation tactics are used here in the wiki article, which have been removed from this example. First, g is a more general function of f(i,i) which is ultimately just a placeholder for the would be function h since for the sake of this argument no other function would be put in it's place. Second, their g uses 0 to denote halt while their h uses 1 to denote halt. Finally, g() and e are exactly the same thing, just e doesn't have it's input explicitly stated. g(e) is the same as e(e) or g(g) )

 

Program e = implementation of function g.

 

From this point two further compositions are proposed. The first one is h(e, e) and the second g(e). These talk about the halting machine run on program e (function g) given itself as input. What happens if you do this? Infinite recursion (not infinite loop) meaning g never returns a result at all.

 

Two other ways of writing this:

The result of program e running on program e is dependent on the result of program e running on program e

 

g(g(g(g(g(g(g(g(g(g(...... forever

 

This infinite recursion occurs regardless of what function g is dependent on (h() or the more general f()). It's just that in the case of it being dependent on h(), they imply a contradiction occurs. h(e,e) a subprogram of g(e), should be returning 0 for doesn't halt. However instead, it's not returning anything because it's too busy infinitely recursing.

[phillip1882]

Kriminal, if you feel the problem is universally solvable, then please write that algorithm. if not, then what make you think it is?

 

here is my challenge to you. write a universal turing machine. then write a halt detector that works for a majority of cases. then write anti halt in the same fashion i have. see what you get when you run halt on anti halt which is run on an abstract algorithm. if you get what i suspect then please drop this already.

[Kriminal99]

Kriminal, if you feel the problem is universally solvable, then please write that algorithm. if not, then what make you think it is?

 

here is my challenge to you. write a universal turing machine. then write a halt detector that works for a majority of cases. then write anti halt in the same fashion i have. see what you get when you run halt on anti halt which is run on an abstract algorithm. if you get what i suspect then please drop this already.

 

The whole point of being smart enough to deal with theory is you don't have to spend time testing stuff that you can easily figure out through reason.

 

Your reasoning is incorrect and has nothing to do with the Turing proof whatsoever. You don't understand Turing's proof. Halt does not give an incorrect answer. It gives the correct answer for the machine it is input. You are simply trying to incorrectly attribute it's answer to the original machine before anti-halt was run on it. But that is not Halt's input. 99% of the people who try to argue with me on this don't even remotely understand Turing's proof.

 

Turing's actual proof can be understood by understanding the following. Machines and their encodings are equivalent. Machine X takes input machine M and runs it with itself as input. Now run machine X on itself. What happens? Infinite recursion. Machine X could do anything else after it's explained function - it doesn't matter because that part would never execute.

 

In theory courses I have taken as exercises we were asked to create Halting machines that worked in the vast majority of cases. When a machine operated within bounded space, we (or at least I did) successfully created Halting algorithms. When it used unbounded amounts of space with any kind of pattern we could successfully create a halting machine.

 

In fact the only cases where you could not create a useful halting machine was in the case where there was no pattern in how it continued to use space. Example: find the first repeated pattern in pi and then stop. The halting machine couldn't do anything but solve the problem first, which would reduce it to the algorithm it was being run on.

 

These cases are a very small percentage of algorithms, and the machine used for the proof was not one of these cases. Instead it was a trivial case where a machine was designed to infinitely recurse and therefore never perform it's basic function. In fact for that matter, it's a proof that the type of construction created in the proof does not have any of the properties of the functions it is composed of. A result that could be useful if seen for what it is.

 

Any universal turing machine substituted for the halting algorithm in that proof would fail to retain it's properties in the construction provided.

[CraigD]

In theory courses I have taken as exercises we were asked to create Halting machines that worked in the vast majority of cases. When a machine operated within bounded space, we (or at least I did) successfully created Halting algorithms. When it used unbounded amounts of space with any kind of pattern we could successfully create a halting machine.

I assume that by “a machine operated within bounded space”, you mean a Turing machine with a tape that does not exceed a given length, or is merely finite.

 

Please provide the state diagram of one or more of the machines you created to solve the halting problem for a “machine operated within bounded space”

 

I’m not disputing that such an algorithm is possible – I’ve even provided a very simple example of one for a special class of machines, in post #2 of A short description of Turing machines and a halting problem undecidability proof. I am skeptical, however, that you have written such a machine, or even a very simple Turing machine, because in a previous thread, Halting Undecidability proof faulty?, you were unwilling to demonstrate even an introductory familiarity with Turing machines, by completing an exercise in writing a simple Turing machine.

 

So, as in those previous threads, I must repeat my challenge to you to show that you know how to write a Turing machine:

Can you write a Turing machine that adds 2 numbers and writes the result to the tape without destroying the original data?

A convention for posting a state diagram, and an example of completing a similar simple exercise appears in the quoted post.

 

If you actual do have the ability to write a Turing machine, either before your refusal to do so in the Halting Undecidability proof faulty?, or because you have taken a class in computing since that thread, you can easily demonstrate it by completing this simple exercise. If not, I must continue to believe you don’t have the basic understanding of computing in general, and Turing machines specifically, to make the claim that people that has read and is convinced by Turing’s 1936 proof of the unsolvability of the halting problem are wrong.

 

I believe you misunderstand Turing’s proof, because you do not understand computing well enough. Assertions of yours such as

The whole point of being smart enough to deal with theory is you don't have to spend time testing stuff that you can easily figure out through reason.

(the implication being that you as smart enough to “deal with theory” in such a way that you don’t have to be able to provide simple proofs by example) are, I believe, very wrong.

 

Understanding theory does not mean you don’t have to “test stuff”. It means you can be reasonably confident that tests of the predictions of a theory that has been successfully tested many times will continue to be successful.

[Kriminal99]

I assume that by “a machine operated within bounded space”, you mean a Turing machine with a tape that does not exceed a given length, or is merely finite.

 

Please provide the state diagram of one or more of the machines you created to solve the halting problem for a “machine operated within bounded space”

 

I’m not disputing that such an algorithm is possible – I’ve even provided a very simple example of one for a special class of machines, in post #2 of A short description of Turing machines and a halting problem undecidability proof. I am skeptical, however, that you have written such a machine, or even a very simple Turing machine, because in a previous thread, Halting Undecidability proof faulty?, you were unwilling to demonstrate even an introductory familiarity with Turing machines, by completing an exercise in writing a simple Turing machine.

 

So, as in those previous threads, I must repeat my challenge to you to show that you know how to write a Turing machine:

 

A convention for posting a state diagram, and an example of completing a similar simple exercise appears in the quoted post.

 

If you actual do have the ability to write a Turing machine, either before your refusal to do so in the Halting Undecidability proof faulty?, or because you have taken a class in computing since that thread, you can easily demonstrate it by completing this simple exercise. If not, I must continue to believe you don’t have the basic understanding of computing in general, and Turing machines specifically, to make the claim that people that has read and is convinced by Turing’s 1936 proof of the unsolvability of the halting problem are wrong.

 

I believe you misunderstand Turing’s proof, because you do not understand computing well enough. Assertions of yours such as

 

(the implication being that you as smart enough to “deal with theory” in such a way that you don’t have to be able to provide simple proofs by example) are, I believe, very wrong.

 

Understanding theory does not mean you don’t have to “test stuff”. It means you can be reasonably confident that tests of the predictions of a theory that has been successfully tested many times will continue to be successful.

 

No one cares what you are skeptical of Craig, and I have nothing to prove to you. You are nobody, and have not demonstrated that you are a competent judge of anything. You just link to wikipedia a lot and misinterpret the arguments there... The class I took was long before the last thread you are linking to as well... You are not in a position to demand that I work trivial exercises for your perverted pleasure. You don't belong on an science forum commenting on people's theoretical arguments using bandwagon and appeal to authority fallacy.

 

Your description of theory is an explanation of why people like you can ever be convinced that what people like me already see so clearly. Theory at it's core has nothing to do with what a group of average people agree with because even though they don't understand the deductive reasoning behind the theory, they have seen the result to be true through experimentation. Theory at it's core is using thought experiments and long chains of deductive reasoning to determine something far beyond the current state of knowledge. And possibly a person equally as capable trying to poke holes in your reasoning, as just because you are certain of something doesn't mean there isn't a possibility you failed to consider.

 

The stupid people proof or experimentation part that you are so fond of is just something you do at the end so that average people can trust what you discovered even though they can't really understand it.

 

 

There are infinite computational models that are equivalent to Turing machines. Using any of these to prove something works just as well as using the Turing machine. There are proofs that the random access memory used by contemporary computers slightly invalidates the use of Turing machines for proofs, but seemingly not in a way that significantly change complexity evaluations so it's ok to use them still. Your obsession with some specific conventions relating to how you were taught to write Turing machines says volumes about how well you understand the subject at a conceptual level.

 

But then that's pretty much been your issue with understanding my posts all along. The Turing machine is a thought experiment. The exact type of tool that allows people like me to create long deductive chains to prove something starting with common facts. If you can't handle thought experiments and long deductive chains you shouldn't be worrying about Turing machine conventions. If you can handle them then you know those conventions are irrelevant because they could all be changed without changing the outcome. The only thing that needs to be addressed are the things I am addressing.

 

operates on limited tape or just doesn't use all of the infinitely long tape ie operates within bounded space... You have to be able to recognize trivial differences in convention and not get hung up on them. Even from one book to another on the subject you will find many such differences. For instance I have written an algorithm that has a continuous input. To evaluate it's complexity, I modded the Turing machine to have a write only head that erases the initial input and replaces it with something else every so often. You can do that, because it doesn't effect the Turing machines validity as a complexity analysis tool. Many authors of various algorithms have done similar things.

 

All the bounded space machine as input halting machine did however was check to see if there was a loop - ie if the machine was in the same state with the same head position and the same tape state. Pretty much how you would check code for an infinite loop. Beyond that I think we may have had some optimization techniques so we didn't have to record every previous total state - but that really doesn't matter.

 

The bounded space requirement guarantees that this is the only time it would not halt. If there isn't a loop like this, but it still doesn't halt, then it would have to use an infinite amount of space. I trust I don't have to give a proof of that...

[phillip1882]

kriminal there are so many things bad about what you wrote i dont even know where to begin.

what you wrote was very offencive to craigD, and doesn't belong here.

all he is asking is you demonstrate some basic knowledge of comp. sci. i don't think that is too much to ask.

you yourself state that testing for a halt condition would require running the algorithm itself in some cases,

so i don't really understand what you're objecting to. either you can create a univeral halt testing machine or you can't.

it's like your saying you disagree with the way turing proved it, but not the result. if that's what you mean then say that.