A Possible "solution" to the Halting Problem
in [Theory]
|
From: Aatu Koskensilta on 21 Oct 2006 10:05 Peter Olcott wrote: > "Aatu Koskensilta" <aatu.koskensilta(a)xortec.fi> wrote in message > news:Egi_g.10440$SA.1402(a)reader1.news.jippii.net... >> Peter Olcott wrote: >>> In order to make it possible for me to make my point, I must insist that the >>> conversation never digresses to tangents until the prerequisite point is >>> made. I have already shown, and it is completely obvious that there is no >>> possible correct YES or NO answer that WillHalt() can possibly provide. >> Sure. I agree. >> >> Let's dance. > > So can you see how this equally applies to the UTM versions of the HP? What are "the UTM versions of HP"? -- Aatu Koskensilta (aatu.koskensilta(a)xortec.fi) "Wovon man nicht sprechen kann, daruber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Peter Olcott on 21 Oct 2006 10:11 "J?n Fairbairn" <jon.fairbairn(a)cl.cam.ac.uk> wrote in message news:wf3b9igcw5.fsf(a)calligramme.charmers... > Patricia Shanahan <pats(a)acm.org> writes: > >> If you take the existence of a decision algorithm for the Halting >> problem as an axiom, while retaining the normal axioms that ultimately >> underly theory of computation, you end up with an inconsistent system of >> axioms. Even then, it is the set of axioms that is broken, not the >> fundamental concept of truth. > > I think this illustrates why reasoned argument is futile in > this thread. The OP /does/ take the existence of a decision > algorthm for the halting problem as an axiom. Consequently, > working from his axioms he can reach any conclusion he > wishes. > > -- > J?n Fairbairn Jon.Fairbairn(a)cl.cam.ac.uk The problem is the mathematical mapping between the conclusions based on the mathematical formalisms and the higher level English language meanings. This problem is caused by arbitrary constraints placed on the formalisms that do not actually exist in the greater context. The only reason that the HP (at least the isolated example that I provided) can not be solved, is that it is merely an ill-formed question. The fact that ill-formed questions lack correct answers should not be elevated to the level of a fundamental theory of computation. (if my isolated example can be generalized).
From: Peter Olcott on 21 Oct 2006 10:17 "Markus Triska" <triska(a)gmx.at> wrote in message news:874ptxzzph.fsf(a)gmx.at... > "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > >> Specifically calling the HP undecidable, is the error. > > It least that terminology is a bit unfortunate, since HP is > semi-decidable. An error would be to infer from its not being > "totally" undecidable (like totality problem for TMs) that it's > decidable. > > Best wishes! > Markus Triska I provided one example that is very close in form to the original problem, that is decidable. The only limitation is that the result of this decision can not be provided as a Boolean return value to every caller. Perhaps if we do not form the artificial contrivance of restricting the form of the result to Boolean, the HP could actually be solved. If WillHalt() is free to provide its result in any form what-so-ever, it could then possibly return the correct result using whatever protocol that LoopIfHalts() is not corrupting.
From: Peter Olcott on 21 Oct 2006 10:21 "Jens Auer" <jens.muaddib(a)googlemail.com> wrote in message news:1161430467.989819.286430(a)m7g2000cwm.googlegroups.com... > > Peter Olcott schrieb: > > >> > But what do you do if I feed in the source code of LoopIfHalts, where I >> > replaced the call to WillHalt with another function (as a source code >> > entity, not a mathematical function) which has the same behaviour (in >> > computational terms, both program compute the same function)? Can your >> > magic function MalignantSelfReference() detect this? >> >> It makes no sense at all to attempt to generalize any point that is not yet >> made. I must restrict all of my responses to the single isolated example that >> I >> have provided, because of the inherent prerequisite order of my points. Only >> after this example is fully analyzed would it make any sense to proceed >> beyond >> this example. If I can't prove my point within the context of this single >> isolated example, then every other point becomes completely moot. > It makes no sense discussing about a solution to a mathematically > formulated problem without having the proposed solution completely > available. If you want to solve the halting problem, formulate a > function which correctly decides if any program terminates on all > inputs. This must work with all programs, not just one example! > Anyway, as others remarked, the prove that you cannot implement halt is > not dependant on a specific halt-function but just assumes that there > is one and shows that this leads to a contradiction. > I think that the isolated single example that I have provided can be mathematically mapped to every other form of the Alan Turing HP. There is no sense going there if people are unwilling to concede the point on this much simpler example. If they don't see the simplest example they won't see the more complex ones.
From: Peter Olcott on 21 Oct 2006 10:22
"Aatu Koskensilta" <aatu.koskensilta(a)xortec.fi> wrote in message news:ZOp_g.10712$545.1166(a)reader1.news.jippii.net... > Peter Olcott wrote: >> "Aatu Koskensilta" <aatu.koskensilta(a)xortec.fi> wrote in message >> news:Egi_g.10440$SA.1402(a)reader1.news.jippii.net... >>> Peter Olcott wrote: >>>> In order to make it possible for me to make my point, I must insist that >>>> the conversation never digresses to tangents until the prerequisite point >>>> is made. I have already shown, and it is completely obvious that there is >>>> no possible correct YES or NO answer that WillHalt() can possibly provide. >>> Sure. I agree. >>> >>> Let's dance. >> >> So can you see how this equally applies to the UTM versions of the HP? > > What are "the UTM versions of HP"? Universal Turing Machine version of the Halting Problem. > > -- > Aatu Koskensilta (aatu.koskensilta(a)xortec.fi) > > "Wovon man nicht sprechen kann, daruber muss man schweigen" > - Ludwig Wittgenstein, Tractatus Logico-Philosophicus |