| olcott <NoOne@NoWhere.com>: Oct 25 03:15PM -0500 On 10/25/2020 12:02 PM, Richard Damon wrote: > If 'Aborted' has no limitations on it, than this halt decider is > worthless, as it could just up and decide that it needs to abort ALL > machines, and if the only test was did it abort it, it would be right. You just really are not paying any attention at all are you? The simplest possible way to define a halt decider is to have the halt decider directly execute its input exactly one execution step / state transition at a time. If we define the halt decider in this simplest possible way then it must stop executing its input as soon as it determines that its input would not otherwise ever halt. -- Copyright 2020 Pete Olcott |
| Elijah Stone <elronnd@elronnd.net>: Oct 25 01:47PM -0700 On Sun, 25 Oct 2020, olcott wrote: > seconds to repeat a prior state. This is only if the code was > intentionally designed to as quickly as possible get into every one of > its possible states. . . . what? It takes a minimum of 0.5ns--a single instruction--'jmp $' or similar. The maximum is: 8gb = (8*1024^3) bits = 2^33 Total states = 2^(2^33) At 2GHz, we can exhaust 2e9 states per second, but let's be generous and make it 2^31, as the math is simpler that way. That makes it: 2^(2^33) --------- 2^31 = 2^(2^33 - 31) = 2^8589934561 seconds. Which is rather mind-bogglingly large. |
| olcott <NoOne@NoWhere.com>: Oct 25 03:51PM -0500 On 10/25/2020 3:41 PM, Richard Damon wrote: > larger capability then the original problem. > This is a well know property, and generally it is said that this method > is unsuitable as a halting decider because of it. This does (as has always been my stated goal) refute all of the conventional self-referential halting problem proofs. None of these proofa show that halting is undecidable they only show that one definition of a halt decider does not work. bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) Every syntaxtically correct machine description can be divided into (a) HAS_INFINITE_EXECUTION (b) DOES_NOT_HAVE_INFINITE_EXECUTION An infinite machine that never returns to the same machine state was not the basis for any of these conventional self-referential halting problem proofs. I have as I have claimed correctly refuted the conventional self-referential halting problem proofs. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 25 03:55PM -0500 On 10/25/2020 3:42 PM, Alan Mackenzie wrote: > alleged halt decider is not possible. That is a mathematical theorem. > If you want to advance this argument, you should call the thing a > "partial halt decider". This does (as has always been my stated goal) refute all of the conventional self-referential halting problem proofs. None of these proofs show that halting is undecidable they only show that one definition of a halt decider does not work. bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) Every syntactically correct machine description can be divided into (a) HAS_INFINITE_EXECUTION (b) DOES_NOT_HAVE_INFINITE_EXECUTION I have as I have claimed correctly refuted the conventional self-referential halting problem proofs. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 25 04:52PM -0500 On 10/25/2020 4:13 PM, Richard Damon wrote: >> self-referential halting problem proofs. > Except you don't refute the proof, you (attempt to) refute a straw man > similar problem. This is decidable: void H_Hat(u32 M) { if (Aborted_Because_Non_Halting_Behavior_Detected(M, M)) MOV_EAX_0 // Execution of M(N) has been aborted else { MOV_EAX_1 // M(N) has halted HERE: goto HERE; } HALT } void H(u32 M, u32 N) { if (Aborted_Because_Non_Halting_Behavior_Detected(M, M)) MOV_EAX_0 // Execution of M(N) has been aborted else MOV_EAX_1 // M(N) has halted HALT } int main() { u32 M = (u32)H_Hat; H(M, M); // MOV_EAX_0 HALT } -- Copyright 2020 Pete Olcott |
| Melzzzzz <Melzzzzz@zzzzz.com>: Oct 25 09:55PM > void H_Hat(u32 M) > { > if (Aborted_Because_Non_Halting_Behavior_Detected(M, M)) Where is implementation of this function? -- current job title: senior software engineer skills: c++,c,rust,go,nim,haskell... press any key to continue or any other to quit... U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec Svi smo svedoci - oko 3 godine intenzivne propagande je dovoljno da jedan narod poludi -- Zli Zec Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi bili naoruzani. -- Mladen Gogala |
| olcott <NoOne@NoWhere.com>: Oct 25 05:14PM -0500 On 10/25/2020 4:33 PM, Richard Damon wrote: > that the Halt Decider, that is ANY Halt Decider (built as a Turing > Machine) can't decide on his machine, he has shown that NO Halt Decider > can be made that meets the requirements of a Halt Decider. When my decider decides his counter-example case his proof is refuted: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) > When I run the machine H(H_Hat, H_Hat) then it gives me an answer by its > terminal state (if it doesn't, it doesn't meet the requirements of a > Halt Decider). We can ask an incorrect question: Is the following sentence: "This sentence is not true." true or false? Or we can rephrase the question so that it has a correct answer: Is the following sentence: "This sentence is not true." true? We can ask the halt deciding question in a way that allows the input program to do the opposite of whatever the halt decider decides: "Does this input program halt on its input (yes or no)?" Or we can ask the halt deciding question in such a way where it is impossible for the input program to do the opposite of what the halt decider decides: When the input program is executed on its input did this execution have to be aborted to prevent infinite execution? Some undecidable problems are only undecidable because we did not phrase the question so that it has a correct answer. Any question that has no correct answer is an incorrect question. The logical law of polar questions copyright 2015 PL Olcott https://groups.google.com/g/sci.lang/c/AO5Vlupeelo/m/nxJy7N2vULwJ -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 25 05:35PM -0500 On 10/25/2020 4:55 PM, Melzzzzz wrote: >> { >> if (Aborted_Because_Non_Halting_Behavior_Detected(M, M)) > Where is implementation of this function? Only the DebugTrace() part of it is fully implemented. Since I have been working on this nearly all the time for about nine months as soon as I got the x86utm operating system fully complete I scaled back my software development to 40 hours per week. http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf I explain exactly how the halt decider works so that H() correctly decides halting of H_Hat(): On 10/25/2020 1:42 PM, olcott wrote: >Aborted_Because_Non_Halting_Behavior_Detected(M, M) twice from the same >machine address without any conditional code in H_Hat() to terminate >this infinite recursion. // The 2018-12-13 @ 7:00 PM solution The above is the key halt deciding decision for this code: void H_Hat(u32 M) { if (DebugTrace(M, M)) MOV_EAX_0 // Execution of M(N) has been aborted else { MOV_EAX_1 // M(N) has halted HERE: goto HERE; } HALT } int main() { u32 M = (u32)H_Hat; H_Hat(M); // MOV_EAX_0 HALT } -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 25 12:23PM -0500 On 10/25/2020 10:36 AM, Malcolm McLean wrote: > emulating. That point has caused difficulty. > However the price of saying that the machine is smashed is that it now becomes > more obvious that something somewhere isn't a Turing machine. In PO's original If we assume that that H_Hat() machine physically exists and is physically destroyed by smashing it with a sledge hammer then this indicates that the machine is not exactly and precisely a Turing machine in every single way. If we understand that: (a) All of the executable code is implemented as von Neumann architecture virtual machines. (b) An operating system function u32* Allocate(u32 size) is provided. (c) The execution of these virtual machines never require more memory than Allocate(u32 size) can allocate. then we can know that the computations of these virtual machines are equivalent to the computations of universal Turing Machines. https://en.wikipedia.org/wiki/Random-access_stored-program_machine > example, that's H_Hat, the act of writing 0 to eax is the step that is disallowed. In Not all all. It is equivalent to the Linz machine transitioning to ((qn)) non-halting behavior detected, would not terminate unless aborted. The outermost H_Hat(H_Hat) that is invoked in the x86utm process context calls DebugTrace(H_Hat, H_Hat) AKA Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) that is also executed in the x86utm process context. This causes DebugTrace(H_Hat, H_Hat) to create a whole new process context to executes its first parameter (the inner H_Hat) in DebugStep() mode. This causes the inner H_Hat to execute an inner DebugTrace(H_Hat, H_Hat) in its own subordinate process context. This inner DebugTrace(H_Hat, H_Hat) creates another whole new process to that executes its first parameter (an inner inner H_Hat) in DebugStep() mode. ------------------------------------------------------ The same sequence can be implemented a Universal Turing Machines instead of von Neumann architecture virtual machines. The master UTM owns the whole tape and allocates portions of this tape to its subordinate UTMs when they are first executed or on request. The master UTM executes the H_Hat() UTM and allocates a portion of its tape to H_Hat(). The H_Hat() UTM executes the DebugTrace() (causing the master UTM to allocate a portion of its master tape to DebugTrace) DebugTrace() executes another instance of H_Hat() is allocated its own separate portion of the master UTM tape. All of the instances of DebugTrace() execute their subordinate UTMs one state transition at a time. As soon as the outermost DebugTrace() detects that its subordinate UTM would not terminate it stops executing it, thus stopping the whole execution tree of UTMs. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 25 12:37PM -0500 On 10/25/2020 11:33 AM, Andy Walker wrote: >>> trying to tell you. >> Most computer programming languages support recursion by allowing a >> function to call itself from within its own code. long int Factorial(int n) { if (n>=1) return n * Factorial((n-1); else return 1; } > that calls itself. Nor, for that matter is the comment "M(M)" if > you re-write it as I suggested, "M.exe(M.src)", where we distinguish > a TM and its actions from the description of that TM. Of course, This would create the problem as it typically is presented with purely arbitrary extraneous complexity. If on the other hand when the Turing Machine Decription language <is> x86 machine language then its description is directly executable. To make things easier to understand the machine language is disassmbled as it executes and can be examined as C before it has been compiled. So YES DebugTrace(H_Hat, H_Hat) does specify infinite recursion and the above two parameters are the machine address of the H_Hat machine code. -- Copyright 2020 Pete Olcott |
| "André G. Isaak" <agisaak@gm.invalid>: Oct 25 12:10PM -0600 On 2020-10-25 11:37, olcott wrote: > arbitrary extraneous complexity. > If on the other hand when the Turing Machine Decription language <is> > x86 machine language then its description is directly executable. x86 machine language is not a "Turing Description Language". > as it executes and can be examined as C before it has been compiled. > So YES DebugTrace(H_Hat, H_Hat) does specify infinite recursion and the > above two parameters are the machine address of the H_Hat machine code. Linz's Ĥ is simply a modified version of Linz's H. Linz's H is a Turing Machine alleged to answer, for a given description of a Turing Machine and a given input, will this TM halt? Nothing in that definition specifies that H (or Ĥ) actually 'executes' that TM description. That's a strategy which you've chosen to adopt, so at best you can claim that *your* specific implementation includes recursion. There's absolutely nothing in Linz's definition which indicates or requires recursion of any kind. So any argument which rests on 'infinite recursion' tells us nothing about the actual Linz proof. André -- To email remove 'invalid' & replace 'gm' with well known Google mail service. |
| olcott <NoOne@NoWhere.com>: Oct 25 01:42PM -0500 On 10/25/2020 11:14 AM, Richard Damon wrote: >> The program under test is no longer executing. > Or we could say that the argument has nothing to do with what a > classical Halt Decider does. We don't need any classical false presumptions and preconceived notions all we need is a function that divides its input into: (a) Would not halt unless aborted. (b) Has already halted. Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) > outer machine that called the decider and takes that results and Halts, > showing the answer to be WRONG, it did not need to be aborted, but was > able to complete within a finite execution. You can keep ignoring what I say yet simply ignoring what I say does not form any rebuttal what-so-ever. Likewise you can read what I say yet simply say that you believe that it is incorrect and this also forms no rebuttal what-so-ever. The following code specifies three entirely different instances of H_Hat() that each have very different amounts of data. Failing to believe this is also no rebuttal what-so-ever. I will soon have code that shows this. void H_Hat(u32 M) { if (Aborted_Because_Non_Halting_Behavior_Detected(M, M)) MOV_EAX_0 // Execution of M(N) has been aborted else { MOV_EAX_1 // M(N) has halted HERE: goto HERE; } HALT } int main() { u32 M = (u32)H_Hat; H_Hat(M); // MOV_EAX_0 HALT } The outermost H_Hat() receives a return value of true from its invocation of Aborted_Because_Non_Halting_Behavior_Detected(M, M). The innermost H_Hat() shows that H_Hat() is infinitely recursive when it calls Aborted_Because_Non_Halting_Behavior_Detected(M, M). This causes the outermost Aborted_Because_Non_Halting_Behavior_Detected(M, M) to abort its inner H_Hat() which terminates the whole process tree that was created and executed from this inner H_Hat(). Only the outermost Aborted_Because_Non_Halting_Behavior_Detected(M, M) has a long enough execution trace to "see" that H_Hat() called Aborted_Because_Non_Halting_Behavior_Detected(M, M) twice from the same machine address without any conditional code in H_Hat() to terminate this infinite recursion. // The 2018-12-13 @ 7:00 PM solution The middle H_Hat() (of three) has its process terminated before its separate, distinct instance of Aborted_Because_Non_Halting_Behavior_Detected(M, M) ever returns a value. So when we are answering the question: Would the input to a halt decider have to have its execution terminated to prevent its infinite execution? The answer of YES always means that the input has non-halting behavior. (a) H(H_Hat, H_Hat) // YES (b) H_Hat(H_Hat) // H_Hat() is not a halt decider -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 25 02:16PM -0500 On 10/25/2020 12:26 PM, Mike Terry wrote: > Calculation A is running some emulation of another calculation B, and at > some point simply decides not to continue the emulating any further. In > this scenario PO says calculation A has "aborted" calculation B. Yes that is precisely correct. When Malcolm says smashing the computer he wants to make it completely clear that with the revised definition of a halt decider the input program cannot possibly do the opposite of whatever the halt decider decided. If my example was implemented using an extension of the Turing Machine Description language provided here: http://www.lns.mit.edu/~dsw/turing/turing.html An "aborted process" would merely mean that the UTM that is executing its subordinate UTM one state transition at a time would stop executing this subordinate UTM and transition to one of its own final states. > [Whether that's a conventional/good use of the term "abort" others can > decide.] It is a very convetional computer science term. Everyone immediately understands that an aborted process utterly ceases all execution. > IMO it adds nothing to say "calculation A has smashed the emulated > machine running B", as this does not help explain anything - if anything It makes it clear for the people that do not know that the term "aborted process" means that a process has utterly stopped all execution and cannot possibly execute another step. > running after it aborts the calculation B. If A is H_Hat(H_Hat), then > the abort does not stop A from continuing and doing the opposite of what > the halt decider decided. Neither an aborted process, nor a smashed computer will ever execute another step. > be aborted in the PO sense, as there is nothing overseeing its execution > to decide to stop executing it. So it always "gets the chance" to do > the opposite of what the halt decider says. No, not at all not in the least. Try and show a concrete example of this and I will point out your false assumption. The outermost H_Hat() is merely a broken version of H(). It is not a halt decider. Anything that it does merely shows the halt deciders can be created incorrectly. >> that H_Hat() cannot do the opposite of what the halt decider decided. > Sprinkling UTM all over the place makes things worse IMO, although the > "simply stops executing it" is clear. The definition of my refutation of the halting problem proofs requires that the halt decider execute its input one state transition at a time. The ONLY TM that can execute another TM at all is a UTM. When we are thinking of this in conventional terms it is simplest to think of ever TM as a UTM so that the entire system only deals with Turing machine Descriptions and never deals with any separate TM. The universal language of x86utm is the x86 machine language that is interpreted by an x86 emulator. > was emulating the H_Hat() calculation simply stops emulating it, so that > the emulated calculation never reaches the point where H_Hat does the > opposite of what its halt decider decided". Perfect! That is the simplest way to say it for everyone that fully understands these terms. Some people might not understand that "the process has been aborted" to mean that the process will not execute any more steps. These people might need the smashed computer analogy. > simply stops emulating it, so that the emulated calculation never > reaches the point where H_Hat does the opposite of what its halt decider > decided" Yes this is also perfect for everyone (like yourself) that fully understands all these terms. > Correct, but for Malcolm's benefit, the halt decider itself continues > running. It has not smashed its own machine. :) > Mike. Actually no. The actual execution trace of H(H_Hat, H_Hat) or H_Hat(H_Hat) has two different instances of the Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) halt decider. All of the processes that are executed in the x86utm master UTM process context cannot be aborted. The second process instance of Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) is executed in the process context created to execute: (H_Hat, H_Hat). This process context is aborted as soon as the outer process context of x86utm Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) decides that H_Hat is infinitely recursive. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 25 03:27PM -0500 On 10/25/2020 1:10 PM, André G. Isaak wrote: >> If on the other hand when the Turing Machine Decription language <is> >> x86 machine language then its description is directly executable. > x86 machine language is not a "Turing Description Language". It is common knowledge that the x86 language implements the von Neumann architecture and that the von Neumann architecture is equivalent to a UTM: https://en.wikipedia.org/wiki/Random-access_stored-program_machine So for all practical purposes the x86 language <is> a UTM description language, thus making x86utm a x86 based UTM operating system. > at best you can claim that *your* specific implementation includes > recursion. There's absolutely nothing in Linz's definition which > indicates or requires recursion of any kind. Yes for all we know the machine specified by Linz might not implement the simplest of all possible halt deciders instead it might always make a phone call to the psychic hotline. There is only one [simplest of all possible halt deciders] thus proving that it is a very execllent basis. If you don't not believe that there is only one [simplest of all possible halt deciders] then provide a counter-example or admit that you cannot. -- Copyright 2020 Pete Olcott |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Oct 20 02:26PM -0700 On 10/20/2020 11:40 AM, olcott wrote: > otherwise terminate. > At the first point that DebugTrace() determines that M(N) would not > otherwise terminate it aborts the DebugStep() of M(N). How does it determine that an unknown function will never terminate? |
| olcott <NoOne@NoWhere.com>: Oct 25 03:42PM -0500 On 10/25/2020 3:27 PM, olcott wrote: > a phone call to the psychic hotline. > There is only one [simplest of all possible halt deciders] thus proving > that it is a very excellent basis. The key aspect of defining a halt decider that executes its input one execution step / state transition at a time to decide: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) Every syntatatically correct machine description can be divided into (a) HAS_INFINITE_EXECUTION (b) DOES_NOT_HAVE_INFINITE_EXECUTION -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 25 03:56PM -0500 On 10/25/2020 3:55 PM, Malcolm McLean wrote: >> running. It has not smashed its own machine. :) > Yes, you have to smash your own machine for the rebuttal of Linz > to work. Otherwise there is no way out. :-( This does (as has always been my stated goal) refute all of the conventional self-referential halting problem proofs. None of these proofs show that halting is undecidable they only show that one definition of a halt decider does not work. bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) Every syntactically correct machine description can be divided into (a) HAS_INFINITE_EXECUTION (b) DOES_NOT_HAVE_INFINITE_EXECUTION I have as I have claimed correctly refuted the conventional self-referential halting problem proofs. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 25 04:07PM -0500 On 10/25/2020 3:55 PM, Richard Damon wrote: > What you don't seem to realize or are refusing to face is WHY the > halting problem, as originally stated, is useful, and why your revised > version, is not. bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) Every syntactically correct machine description can be divided into (a) HAS_INFINITE_EXECUTION (b) DOES_NOT_HAVE_INFINITE_EXECUTION I have as I have claimed correctly refuted the conventional self-referential halting problem proofs. There are no inputs that can be shown to be undecidable. There are no inputs that can be shown to be undecidable. There are no inputs that can be shown to be undecidable. There are no inputs that can be shown to be undecidable. > to run in a more convenient form that has computational equivalence to a > Turning machine, and then make arguments about that Turing machine, > without needed to actually convert the algorithm into a Turning Machine. x86 language ≡ von Neumann architecture ≡ UTM > because the numbers got too big and you ran out of memory, which doesn't > mean that no solution exists, it just establishes a lower bound for a > solution. I have never said that I solved the halting problem. I have always said that I have refuted the conventional self-referential halting problem proofs. I really have done that and no one can show otherwise. I really have done that and no one can show otherwise. I really have done that and no one can show otherwise. I really have done that and no one can show otherwise. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 25 04:55PM -0500 On 10/25/2020 4:35 PM, Richard Damon wrote: >> to work. Otherwise there is no way out. :-( > except then you don't have the required halt decider because it never > answered the question, bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) Cannot be fooled by pathological self reference. -- Copyright 2020 Pete Olcott |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment