Total Posts:12Showing Posts:112
Question about the Halting Problem
Posts: 13,034
Add as Friend Challenge to a Debate Send a Message 
4/18/2016 3:43:30 AM Posted: 1 year 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? "In case anyone hasn't noticed it, the West is in extremis. The undertaker is checking his watch at the foot of its bed, and there's a sinister kettle of croaking, moneyfeathered vultures on the roof." 
Posts: 3,749
Add as Friend Challenge to a Debate Send a Message 
4/18/2016 12:23:54 PM Posted: 1 year ago At 4/18/2016 3:43:30 AM, dylancatlow wrote: 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 selfreferential paradox, the selfreferential 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 selfreferential, 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 selfreferential 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 
Posts: 3,724
Add as Friend Challenge to a Debate Send a Message 
4/18/2016 1:10:58 PM Posted: 1 year 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.

Posts: 13,034
Add as Friend Challenge to a Debate Send a Message 
4/18/2016 1:22:56 PM Posted: 1 year ago At 4/18/2016 12:23:54 PM, Sidewalker wrote:At 4/18/2016 3:43:30 AM, dylancatlow wrote: 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." "In case anyone hasn't noticed it, the West is in extremis. The undertaker is checking his watch at the foot of its bed, and there's a sinister kettle of croaking, moneyfeathered vultures on the roof." 
Posts: 3,724
Add as Friend Challenge to a Debate Send a Message 
4/18/2016 9:37:42 PM Posted: 1 year ago So is this about Turing's actual paper or not?

Posts: 13,034
Add as Friend Challenge to a Debate Send a Message 
4/18/2016 9:55:54 PM Posted: 1 year ago At 4/18/2016 9:37:42 PM, keithprosser wrote: 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. "In case anyone hasn't noticed it, the West is in extremis. The undertaker is checking his watch at the foot of its bed, and there's a sinister kettle of croaking, moneyfeathered vultures on the roof." 
Posts: 1,096
Add as Friend Challenge to a Debate Send a Message 
4/18/2016 10:05:38 PM Posted: 1 year ago At 4/18/2016 9:55:54 PM, dylancatlow wrote:At 4/18/2016 9:37:42 PM, keithprosser wrote: nice CYA there, is that SOP for talking about what you don't know what you are talking about? 
Posts: 13,034
Add as Friend Challenge to a Debate Send a Message 
4/18/2016 10:07:17 PM Posted: 1 year 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: Your sentence is scarcely coherent. But I'm sure you're already aware of that. "In case anyone hasn't noticed it, the West is in extremis. The undertaker is checking his watch at the foot of its bed, and there's a sinister kettle of croaking, moneyfeathered vultures on the roof." 
Posts: 3,749
Add as Friend Challenge to a Debate Send a Message 
4/19/2016 2:30:09 AM Posted: 1 year 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: 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 selfreferential 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 selfreferential in the same way that "This sentence is false" is selfreferential, 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. No, I don't think he does, the CTMU is filled with selfreferential paradox as some of it's basic principles, he spends a lot of time simply ignoring the implicit logical contradictions within selfreference. The CTMU has things containing each other, selfcontained and selfactualizing processes, selfprocessing information, operators that process themselves, selfdeterminacy, selfselection, 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 selfcontradiction 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 
Posts: 13,034
Add as Friend Challenge to a Debate Send a Message 
4/19/2016 6:17:33 PM Posted: 1 year 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? 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. 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 openended 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 selfreference, i.e. cognition). A paradox whose definition seems to preclude such stratification is merely a selfannihilating 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 selfreference in a selfcontained mathematical structure called SelfConfiguring SelfProcessing 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 "selfresolving paradox" (the paradox is "selfresolving" 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."
Langan explicitly says that his theory is not complete. Once again, your knowledge of the CTMU appears to be quite nonexistent. "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" "In case anyone hasn't noticed it, the West is in extremis. The undertaker is checking his watch at the foot of its bed, and there's a sinister kettle of croaking, moneyfeathered vultures on the roof." 
Posts: 3,749
Add as Friend Challenge to a Debate Send a Message 
4/20/2016 1:12:50 AM Posted: 1 year 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: 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.
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. You see, that's what I'm talking about, preposterous gobbledegook jargon, and nope, it's not logical and it doesn't mean anything.
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 selfcontained (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." 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 
Posts: 9,232
Add as Friend Challenge to a Debate Send a Message 
4/20/2016 3:12:24 AM Posted: 1 year ago This sounds like how the the majority of my co workers think
