Total Posts:12|Showing Posts:1-12
Jump to topic:

Question about the Halting Problem

dylancatlow
Posts: 12,255
Add as Friend
Challenge to a Debate
Send a Message
4/18/2016 3:43:30 AM
Posted: 7 months ago
In 1936 Alan Turing proved that it is impossible to create an algorithm for determining whether a given program would halt or continue to run forever on a given input. To do this, he employed the technique of reductio ad absurdum by showing that if such an algorithm were to exist, it could be altered in such a way that if one were to feed it into itself -- ask the algorithm whether it would halt on a given input -- any answer it gives would necessarily undermine its own validity. The altered program is to be exactly the same as the original in all but one respect: it has additional instructions on what to do once an answer has been reached. If it is thought that a given program would halt on some input, then the altered program (H+ for short) is to loop forever (not halt) while if it is thought that a given program would continue running forever on a given input, then H+ is to halt. When H+ attempts to calculate whether it would halt on a given input strange things start to happen. If it thinks it would halt, then it's supposed to loop forever in which case it doesn't halt. Conversely, if it thinks it would continue running forever then it's supposed to halt in which case it doesn't run forever. No matter what answer H+ comes up with it's always wrong, because the answer is no longer valid once H+ acts on its additional instructions.

The part I don't get is why the failure of H+ to do its job has any relevance to the original algorithm. Can someone please explain Turing's reasoning?
Sidewalker
Posts: 3,713
Add as Friend
Challenge to a Debate
Send a Message
4/18/2016 12:23:54 PM
Posted: 7 months ago
At 4/18/2016 3:43:30 AM, dylancatlow wrote:
In 1936 Alan Turing proved that it is impossible to create an algorithm for determining whether a given program would halt or continue to run forever on a given input. To do this, he employed the technique of reductio ad absurdum by showing that if such an algorithm were to exist, it could be altered in such a way that if one were to feed it into itself -- ask the algorithm whether it would halt on a given input -- any answer it gives would necessarily undermine its own validity. The altered program is to be exactly the same as the original in all but one respect: it has additional instructions on what to do once an answer has been reached. If it is thought that a given program would halt on some input, then the altered program (H+ for short) is to loop forever (not halt) while if it is thought that a given program would continue running forever on a given input, then H+ is to halt. When H+ attempts to calculate whether it would halt on a given input strange things start to happen. If it thinks it would halt, then it's supposed to loop forever in which case it doesn't halt. Conversely, if it thinks it would continue running forever then it's supposed to halt in which case it doesn't run forever. No matter what answer H+ comes up with it's always wrong, because the answer is no longer valid once H+ acts on its additional instructions.

The part I don't get is why the failure of H+ to do its job has any relevance to the original algorithm. Can someone please explain Turing's reasoning?

Because the original algorithm was testing whether or not a program, any program, could be devised that would determine whether or not the program in question would halt. So the fact that he proved a program that contains the program sets up a paradox which under the rules of logic and mathematics makes it undecidable, establishes that no solution can exist.

The halting problem is about limits, it says there are limits to what can be computed, just as Godel's Incompleteness Theorem stablishes that there are limits to what any axiomatic system can do, and it's why Bertram Russell's simple barber question completely demolished Gottlob Frege's Logicism. Essentially, they all are about limitation and the solution/proof for all of them come down to the self-referential paradox, the self-referential paradox brings down every attempt to make a formal system complete, or unlimited.

In the end, they are all just complicated variations on the oldest paradox in the book, which is establishing the truth of the sentence "This sentence is false". Because it is self-referential, there is no correct answer, if it's true it's false and if it's false it's true. Bertram Russell made the same point with the barber question, Turing made it with the halting problem, and Godel made it with the incompleteness Theorem. In mathematics, logic, computing, or in any axiomatic system for that matter, the self-referential paradox obliterates any attempt to make any formal system unlimited in scope, there can be no perfect formal system.

There is just no way past it, despite the logical and semantic shenanigans of your boy Chris Langan, which I'm sure is why you are looking into the halting problem in the first place. In the end, Langan's entire house of cards is an attempt at getting past the self referential paradox with slick semantics games, but logic just doesn't work that way.
"It is one of the commonest of mistakes to consider that the limit of our power of perception is also the limit of all there is to perceive." " C. W. Leadbeater
keithprosser
Posts: 2,085
Add as Friend
Challenge to a Debate
Send a Message
4/18/2016 1:10:58 PM
Posted: 7 months ago
Having downloaded Turing's paper and gone through it I can't find anything that matches the description in the op, a reference to the actual page rather than a vague paraphrase would help.
dylancatlow
Posts: 12,255
Add as Friend
Challenge to a Debate
Send a Message
4/18/2016 1:22:56 PM
Posted: 7 months ago
At 4/18/2016 12:23:54 PM, Sidewalker wrote:
At 4/18/2016 3:43:30 AM, dylancatlow wrote:
In 1936 Alan Turing proved that it is impossible to create an algorithm for determining whether a given program would halt or continue to run forever on a given input. To do this, he employed the technique of reductio ad absurdum by showing that if such an algorithm were to exist, it could be altered in such a way that if one were to feed it into itself -- ask the algorithm whether it would halt on a given input -- any answer it gives would necessarily undermine its own validity. The altered program is to be exactly the same as the original in all but one respect: it has additional instructions on what to do once an answer has been reached. If it is thought that a given program would halt on some input, then the altered program (H+ for short) is to loop forever (not halt) while if it is thought that a given program would continue running forever on a given input, then H+ is to halt. When H+ attempts to calculate whether it would halt on a given input strange things start to happen. If it thinks it would halt, then it's supposed to loop forever in which case it doesn't halt. Conversely, if it thinks it would continue running forever then it's supposed to halt in which case it doesn't run forever. No matter what answer H+ comes up with it's always wrong, because the answer is no longer valid once H+ acts on its additional instructions.

The part I don't get is why the failure of H+ to do its job has any relevance to the original algorithm. Can someone please explain Turing's reasoning?

Because the original algorithm was testing whether or not a program, any program, could be devised that would determine whether or not the program in question would halt. So the fact that he proved a program that contains the program sets up a paradox which under the rules of logic and mathematics makes it undecidable, establishes that no solution can exist.

No, the original algorithm was not testing whether such a program exists, it is the program. And the only reason it's undecidable is that H+ is the program trying to determine the solution. H+ is not exhaustive of all possible programs, as it contains certain unnecessary instructions. Is the idea simply that the original program can't claim to be compromised due to the additional instructions, and thus ought to be able to perform its job even when contained inside of a larger program?

There is just no way past it, despite the logical and semantic shenanigans of your boy Chris Langan, which I'm sure is why you are looking into the halting problem in the first place. In the end, Langan's entire house of cards is an attempt at getting past the self referential paradox with slick semantics games, but logic just doesn't work that way.

You do realize that Langan accepts both the implications of Godel's proof and Turing's proof, right?

"As part of his Erlangen Program for 20th century mathematics, the eminent German mathematician David Hilbert had wanted to ascertain that mathematics is "complete" when formalized in a system like the predicate calculus"i.e., that all true theorems (and no false ones) can be proven. But after helpfully setting out to show that every true formula expressed in the predicate calculus is provable, Kurt Godel sadly arrived at a different conclusion. As it turns out, not even arithmetic is complete in this sense. In any consistent formal system containing arithmetic, there are true but unprovable statements. Although their truth can be directly apprehended, they cannot be formally derived from a finite set of axioms in a stepwise fashion."
dylancatlow
Posts: 12,255
Add as Friend
Challenge to a Debate
Send a Message
4/18/2016 9:55:54 PM
Posted: 7 months ago
At 4/18/2016 9:37:42 PM, keithprosser wrote:
So is this about Turing's actual paper or not?

I didn't even read Turing's paper, I'm just going off of what people have said about it. If I misrepresented Turing's argument then feel free to explain how.
DPMartin
Posts: 1,096
Add as Friend
Challenge to a Debate
Send a Message
4/18/2016 10:05:38 PM
Posted: 7 months ago
At 4/18/2016 9:55:54 PM, dylancatlow wrote:
At 4/18/2016 9:37:42 PM, keithprosser wrote:
So is this about Turing's actual paper or not?

I didn't even read Turing's paper, I'm just going off of what people have said about it. If I misrepresented Turing's argument then feel free to explain how.

nice CYA there, is that SOP for talking about what you don't know what you are talking about?
dylancatlow
Posts: 12,255
Add as Friend
Challenge to a Debate
Send a Message
4/18/2016 10:07:17 PM
Posted: 7 months ago
At 4/18/2016 10:05:38 PM, DPMartin wrote:
At 4/18/2016 9:55:54 PM, dylancatlow wrote:
At 4/18/2016 9:37:42 PM, keithprosser wrote:
So is this about Turing's actual paper or not?

I didn't even read Turing's paper, I'm just going off of what people have said about it. If I misrepresented Turing's argument then feel free to explain how.

nice CYA there, is that SOP for talking about what you don't know what you are talking about?

Your sentence is scarcely coherent. But I'm sure you're already aware of that.
Sidewalker
Posts: 3,713
Add as Friend
Challenge to a Debate
Send a Message
4/19/2016 2:30:09 AM
Posted: 7 months ago
At 4/18/2016 1:22:56 PM, dylancatlow wrote:
At 4/18/2016 12:23:54 PM, Sidewalker wrote:
At 4/18/2016 3:43:30 AM, dylancatlow wrote:
In 1936 Alan Turing proved that it is impossible to create an algorithm for determining whether a given program would halt or continue to run forever on a given input. To do this, he employed the technique of reductio ad absurdum by showing that if such an algorithm were to exist, it could be altered in such a way that if one were to feed it into itself -- ask the algorithm whether it would halt on a given input -- any answer it gives would necessarily undermine its own validity. The altered program is to be exactly the same as the original in all but one respect: it has additional instructions on what to do once an answer has been reached. If it is thought that a given program would halt on some input, then the altered program (H+ for short) is to loop forever (not halt) while if it is thought that a given program would continue running forever on a given input, then H+ is to halt. When H+ attempts to calculate whether it would halt on a given input strange things start to happen. If it thinks it would halt, then it's supposed to loop forever in which case it doesn't halt. Conversely, if it thinks it would continue running forever then it's supposed to halt in which case it doesn't run forever. No matter what answer H+ comes up with it's always wrong, because the answer is no longer valid once H+ acts on its additional instructions.

The part I don't get is why the failure of H+ to do its job has any relevance to the original algorithm. Can someone please explain Turing's reasoning?

Because the original algorithm was testing whether or not a program, any program, could be devised that would determine whether or not the program in question would halt. So the fact that he proved a program that contains the program sets up a paradox which under the rules of logic and mathematics makes it undecidable, establishes that no solution can exist.

No, the original algorithm was not testing whether such a program exists, it is the program.

Yeah, but it is the program that determines whether another given program will halt or not, it's explicitly designed to test other programs regarding the halting problem. By making it circular, which is to say by making the program the input to itself, he set up the self-referential paradox, so if it halts, it doesn't halt and vice versa. It's a complex version of the "This sentence is false" paradox.

And the only reason it's undecidable is that H+ is the program trying to determine the solution. H+ is not exhaustive of all possible programs, as it contains certain unnecessary instructions. Is the idea simply that the original program can't claim to be compromised due to the additional instructions, and thus ought to be able to perform its job even when contained inside of a larger program?

No, essentially he made it self-referential in the same way that "This sentence is false" is self-referential, if the program halts, it doesn't halt, and if it doesn't halt, it halts. So does it halt or not? The answer is there is no answer, just as there is no answer to the question of whether the sentence is true or false.

There is just no way past it, despite the logical and semantic shenanigans of your boy Chris Langan, which I'm sure is why you are looking into the halting problem in the first place. In the end, Langan's entire house of cards is an attempt at getting past the self referential paradox with slick semantics games, but logic just doesn't work that way.

You do realize that Langan accepts both the implications of Godel's proof and Turing's proof, right?

No, I don't think he does, the CTMU is filled with self-referential paradox as some of it's basic principles, he spends a lot of time simply ignoring the implicit logical contradictions within self-reference. The CTMU has things containing each other, self-contained and self-actualizing processes, self-processing information, operators that process themselves, self-determinacy, self-selection, things mapped, generated, or replicated within themselves, the list of contradictions goes on and on.

The fact is, Langan claims the CTMU is an axiomatic system that constitutes absolute truth, and it is supposedly a logical framework for a Theory of Everything, both of which directly contradict Godel's incompleteness theorem. It is a contradiction to say he accepts Godel's proof when he also asserts that the CTMU circumvents its proven limitations to achieve absolute truth. Godel proved you can't have a formalized axiomatic system that is complete and consistent, Langan claims his system is just that, it is yet another CTMU self-contradiction that Langan also claims to accept the implications of Godel's proof.
"It is one of the commonest of mistakes to consider that the limit of our power of perception is also the limit of all there is to perceive." " C. W. Leadbeater
dylancatlow
Posts: 12,255
Add as Friend
Challenge to a Debate
Send a Message
4/19/2016 6:17:33 PM
Posted: 7 months ago
At 4/19/2016 2:30:09 AM, Sidewalker wrote:
At 4/18/2016 1:22:56 PM, dylancatlow wrote:
The part I don't get is why the failure of H+ to do its job has any relevance to the original algorithm. Can someone please explain Turing's reasoning?

Because the original algorithm was testing whether or not a program, any program, could be devised that would determine whether or not the program in question would halt. So the fact that he proved a program that contains the program sets up a paradox which under the rules of logic and mathematics makes it undecidable, establishes that no solution can exist.

No, the original algorithm was not testing whether such a program exists, it is the program.

Yeah, but it is the program that determines whether another given program will halt or not, it's explicitly designed to test other programs regarding the halting problem. By making it circular, which is to say by making the program the input to itself, he set up the self-referential paradox, so if it halts, it doesn't halt and vice versa. It's a complex version of the "This sentence is false" paradox.

The point is that the paradox only manifests itself once the program is coupled with additional instructions, at which point it is unclear (to me at least) whether it's still appropriate to treat the program, now embedded in a larger program, the same way it was originally defined, in which case no paradox is shown to result from the theoretical existence of the original program as it's not even implicated in the hypothetical scenario.

There is just no way past it, despite the logical and semantic shenanigans of your boy Chris Langan, which I'm sure is why you are looking into the halting problem in the first place. In the end, Langan's entire house of cards is an attempt at getting past the self referential paradox with slick semantics games, but logic just doesn't work that way.

You do realize that Langan accepts both the implications of Godel's proof and Turing's proof, right?

No, I don't think he does, the CTMU is filled with self-referential paradox as some of it's basic principles, he spends a lot of time simply ignoring the implicit logical contradictions within self-reference. The CTMU has things containing each other, self-contained and self-actualizing processes, self-processing information, operators that process themselves, self-determinacy, self-selection, things mapped, generated, or replicated within themselves, the list of contradictions goes on and on.

This is completely ridiculous. The CTMU was developed in part so that such paradoxes could be resolved. The notion that Langan simply ignores such paradoxes is just crazy talk.

" Such paradoxes are properly viewed not as static objects, but as dynamic alternations associated with a metalinguistic stratification that is constructively open-ended but transfinitely closed (note that this is also how we view the universe). Otherwise, the paradox corrupts the informational boundary between true and false and thus between all logical predicates and their negations, which of course destroys all possibility of not only its cognitive resolution, but cognition and perception themselves. Yet cognition and perception exist, implying that nature contrives to resolve such paradoxes wherever they might occur. In fact, the value of such a paradox is that it demonstrates the fundamental necessity for reality to incorporate a ubiquitous relativization mechanism for its resolution, namely the aforementioned metalinguistic stratification of levels of reference (including levels of self-reference, i.e. cognition). A paradox whose definition seems to preclude such stratification is merely a self-annihilating construct that violates the "syntax" (structural and inferential rules) of reality and therefore lacks a real model.

In other words, to describe reality as cognitive, we must stratify cognition and organize the resulting levels of self-reference in a self-contained mathematical structure called Self-Configuring Self-Processing Language or SCSPL. SCSPL, which consists of a monic, recursive melding of information and cognition called infocognition, incorporates a metalogical axiom, Multiplex Unity or MU, that characterizes the universe as a syndiffeonic relation or "self-resolving paradox" (the paradox is "self-resolving" by virtue of SCSPL stratification). A syndiffeonic relation is just a universal quantum of inductive and deductive processing, i.e. cognition, whereby "different" objects are acknowledged to be "the same" with respect to their mutual relatedness."


The fact is, Langan claims the CTMU is an axiomatic system that constitutes absolute truth, and it is supposedly a logical framework for a Theory of Everything, both of which directly contradict Godel's incompleteness theorem. It is a contradiction to say he accepts Godel's proof when he also asserts that the CTMU circumvents its proven limitations to achieve absolute truth. Godel proved you can't have a formalized axiomatic system that is complete and consistent, Langan claims his system is just that, it is yet another CTMU self-contradiction that Langan also claims to accept the implications of Godel's proof.

Langan explicitly says that his theory is not complete. Once again, your knowledge of the CTMU appears to be quite non-existent.

"In other words, the means by which the theory is constructed must be rational and tautological, while those by which it is subsequently refined may be empirical. Since we want our theory to be inclusive enough, exclusive enough and consistent enough to do the job of describing reality, these properties will certainly include comprehensiveness (less thorough but also less undecidable than completeness), closure, and consistency."

"In contrast, the CTMU deals directly with the outstanding paradoxes and fundamental interrelationship of mathematics and physics. Unlike other TOEs, the CTMU does not purport to be a "complete" theory; there are too many physical details and undecidable mathematical theorems to be accounted for (enough to occupy whole future generations of mathematicians and scientists), and merely stating a hypothetical relationship among families of subatomic particles is only a small part of the explanatory task before us. Instead, the CTMU is merely designed to be consistent and comprehensive at a high level of generality, a level above that at which most other TOEs are prematurely aimed"
Sidewalker
Posts: 3,713
Add as Friend
Challenge to a Debate
Send a Message
4/20/2016 1:12:50 AM
Posted: 7 months ago
At 4/19/2016 6:17:33 PM, dylancatlow wrote:
At 4/19/2016 2:30:09 AM, Sidewalker wrote:
At 4/18/2016 1:22:56 PM, dylancatlow wrote:

The point is that the paradox only manifests itself once the program is coupled with additional instructions, at which point it is unclear (to me at least) whether it's still appropriate to treat the program, now embedded in a larger program, the same way it was originally defined, in which case no paradox is shown to result from the theoretical existence of the original program as it's not even implicated in the hypothetical scenario.

I don't know what Halting Problem you are talking about, the one I was talking about was the Turing Halting Problem that addresses whether a given program and its input will complete or run forever. What Alan Turing proved was that a general algorithm for making such a determination for any arbitrary program and input cannot exist. The proof involved demonstrating that the problem has no solution when the program itself is also the input to the program.

I'm not sure why this special case of a program that isn't paradoxical and whether or not it halts can be determined is significant to you, but it's something of a irrelevant tangent to the halting problem. There are plenty of programs that either halt or loop, and plenty of ways to prove that about those programs, but that really isn't what the halting problem was about. It was about whether or not a general program that could make a halting determination for any program and input could exist. Turns out it can't, and Turing proved it.

You do realize that Langan accepts both the implications of Godel's proof and Turing's proof, right?

No, I don't think he does, the CTMU is filled with self-referential paradox as some of it's basic principles, he spends a lot of time simply ignoring the implicit logical contradictions within self-reference. The CTMU has things containing each other, self-contained and self-actualizing processes, self-processing information, operators that process themselves, self-determinacy, self-selection, things mapped, generated, or replicated within themselves, the list of contradictions goes on and on.

This is completely ridiculous. The CTMU was developed in part so that such paradoxes could be resolved. The notion that Langan simply ignores such paradoxes is just crazy talk.

He claims to resolve logical paradoxes and then uses preposterous gobbledegook jargon and semantic bait and switch techniques, that is the crazy talk, and nope, that crazy talk is not logical, and it doesn't resolve anything.

" Such paradoxes are properly viewed not as static objects, but as dynamic alternations associated with a metalinguistic stratification that is constructively open-ended but transfinitely closed (note that this is also how we view the universe). Otherwise, the paradox corrupts the informational boundary between true and false and thus between all logical predicates and their negations, which of course destroys all possibility of not only its cognitive resolution, but cognition and perception themselves. Yet cognition and perception exist, implying that nature contrives to resolve such paradoxes wherever they might occur. In fact, the value of such a paradox is that it demonstrates the fundamental necessity for reality to incorporate a ubiquitous relativization mechanism for its resolution, namely the aforementioned metalinguistic stratification of levels of reference (including levels of self-reference, i.e. cognition). A paradox whose definition seems to preclude such stratification is merely a self-annihilating construct that violates the "syntax" (structural and inferential rules) of reality and therefore lacks a real model.

In other words, to describe reality as cognitive, we must stratify cognition and organize the resulting levels of self-reference in a self-contained mathematical structure called Self-Configuring Self-Processing Language or SCSPL. SCSPL, which consists of a monic, recursive melding of information and cognition called infocognition, incorporates a metalogical axiom, Multiplex Unity or MU, that characterizes the universe as a syndiffeonic relation or "self-resolving paradox" (the paradox is "self-resolving" by virtue of SCSPL stratification). A syndiffeonic relation is just a universal quantum of inductive and deductive processing, i.e. cognition, whereby "different" objects are acknowledged to be "the same" with respect to their mutual relatedness."

You see, that's what I'm talking about, preposterous gobbledegook jargon, and nope, it's not logical and it doesn't mean anything.

It is a contradiction to say he accepts Godel's proof when he also asserts that the CTMU circumvents its proven limitations to achieve absolute truth. Godel proved you can't have a formalized axiomatic system that is complete and consistent, Langan claims his system is just that, it is yet another CTMU self-contradiction that Langan also claims to accept the implications of Godel's proof.

Langan explicitly says that his theory is not complete. Once again, your knowledge of the CTMU appears to be quite non-existent.

Tell it to Chris Langan and the folks at CTMU Wiki.

"I am closer to absolute truth than any man has been before me" - Chris Langan

"It (the CTMU) is meant only to provide a comprehensive, consistent and self-contained (and to that extent "absolute") logical framework"" - Chris Langan - On Absolute Truth and Knowledge

"Among his (Langan"s) claims for the theory are that it constitutes absolute truth, provides the logical framework of a Theory of Everything, and proves the existence of God." " CTMU Wiki

"In other words, the means by which the theory is constructed must be rational and tautological, while those by which it is subsequently refined may be empirical. Since we want our theory to be inclusive enough, exclusive enough and consistent enough to do the job of describing reality, these properties will certainly include comprehensiveness (less thorough but also less undecidable than completeness), closure, and consistency."

"In contrast, the CTMU deals directly with the outstanding paradoxes and fundamental interrelationship of mathematics and physics. Unlike other TOEs, the CTMU does not purport to be a "complete" theory; there are too many physical details and undecidable mathematical theorems to be accounted for (enough to occupy whole future generations of mathematicians and scientists), and merely stating a hypothetical relationship among families of subatomic particles is only a small part of the explanatory task before us. Instead, the CTMU is merely designed to be consistent and comprehensive at a high level of generality, a level above that at which most other TOEs are prematurely aimed"

Yeah, Langan talks a lot about what he has accomplished, but the fact is, he doesn't accomplish it, it's all hype and no substance, semantics games mixed with idealism aren't solutions to Hilbert"s Program, he didn't prove formalism, and he hasn't resolved the foundational problems of mathematics and physics. You have to do a lot more than make blathering declarations that you did it.

Langan talks a lot about what he has accomplished, but the fact is, he doesn't accomplish it, it's all hype and no substance, semantics games mixed with idealism aren't solutions to Hilbert's Program, he didn't prove formalism, and he hasn't resolved the foundational problems of mathematics and physics. To do that, you have to do a lot more than make blathering declarations that you did it.

Do you really think Bouncer Boy resolved all of the foundational issue of Mathematics and Physics back in the 1980s and to this day. nobody has noticed except for the galactically gullible internet kooks? Seriously?
"It is one of the commonest of mistakes to consider that the limit of our power of perception is also the limit of all there is to perceive." " C. W. Leadbeater
sadolite
Posts: 8,842
Add as Friend
Challenge to a Debate
Send a Message
4/20/2016 3:12:24 AM
Posted: 7 months ago
This sounds like how the the majority of my co workers think
It's not your views that divide us, it's what you think my views should be that divides us.

If you think I will give up my rights and forsake social etiquette to make you "FEEL" better you are sadly mistaken

If liberal democrats would just stop shooting people gun violence would drop by 90%