| Mike Terry <news.dead.person.stones@darjeeling.plus.com>: Oct 21 02:57AM +0100 On 20/10/2020 19:40, 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). OK. I've added a valid implementation for H_Hat below. I've also added an appropriate invocation for H_Hat in main(), but obviously main() will only actually invoke one or the other, depending on whether we've built the "run H" or "run H_Hat" machine. (Hopefully this is equivalent to what you are doing... My actual question at the end.) > - int Abort = DebugTrace(M, N); > - if (Abort) > - { // DebugTrace says M(M) does not halt > - } > - else > - { // DebugTrace says M(M) halts > - } > - } > - int H_Hat(u32 M) { int Abort = DebugTrace(M, M); if (Abort) { // DebugTrace says M(M) does not halt HALT // ..so we halt } else { // DebugTrace says M(M) halts for (;;); // ..so we loop } } > - int main() > - { > - u32 M = (u32)H_Hat; # ifdef RUN_H > - H(M, M); // run H (H_Hat, H_Hat) # else H_Hat (M); // run H_Hat (H_Hat) # endif > - HALT; > - } So there are two execution contexts to consider where DebugTrace is called - either from within H, or from within H_Hat. (Yes, these will actually be in different "machines".) In both contexts, the DebugTrace call receives the same parameters (H_Hat, H_Hat). Can you confirm that in both the above execution paths, the DebugTrace(H_Hat, H_Hat) returns the same return code? I don't know what's in your DebugTrace(), but unless it's blatently cheating it will return the same result if called with the same parameters, right? Regards, Mike. |
| olcott <NoOne@NoWhere.com>: Oct 20 10:07PM -0500 On 10/20/2020 8:57 PM, Mike Terry wrote: > built the "run H" or "run H_Hat" machine. > (Hopefully this is equivalent to what you are doing... My actual > question at the end.) I liked your simplest possible H_Hat() so I used it. Immediately before I saw your simplest possible H_Hat() I had just reduced the complexity of mine to be exactly the same so we are of one mind on this. // M has address of H_Hat() int H_Hat(u32 M) { int Abort = DebugTrace(M, M); if (Abort) { MOV_EAX_0 // DebugTrace says that M(M) HALT // has been aborted } else { MOV_EAX_1 // M(M) has halted HERE: goto HERE; HALT } } // M and N have the address of H_Hat() int H(u32 M, u32 N) { int Abort = DebugTrace(M, N); if (Abort) { MOV_EAX_0 // DebugTrace says that M(N) HALT // has been aborted } else { MOV_EAX_1 // M(N) has halted HALT } } int main() { u32 M = (u32)H_Hat; H(M, M); HALT; } To make things easy I provided the actual code. We don't need any compile time switch to execute H() and H_Hat(). H() executes H_Hat() in DebugTrace() mode which causes H_Hat() to execute itself in DebugTrace() mode. The invocation of H() is in one process context, the first invocation of H_Hat() is in another process context, and the second invocation of H_Hat() is in the third process context. > call receives the same parameters (H_Hat, H_Hat). > Can you confirm that in both the above execution paths, the > DebugTrace(H_Hat, H_Hat) returns the same return code? Yes. -- Copyright 2020 Pete Olcott |
| Mike Terry <news.dead.person.stones@darjeeling.plus.com>: Oct 21 04:28PM +0100 On 21/10/2020 04:07, olcott wrote: > } > To make things easy I provided the actual code. > We don't need any compile time switch to execute H() and H_Hat(). In the Linz proof, there are two separate TMs whose execution is considered: H which runs with input (H^, H^), and halts in an accept state or in a reject state H^ which runs with input (H^) and either halts or never halts These two TMs, in your C program world, correspond to two COFF files: one for H and one for H^. In my example you could generate the two COFF files by defining (or not) the preprocessor symbol RUN_H. The C code used for both COFF files is the same. You have given the code for the H COFF file, and say there is no need for any precompiler symbols, but you have not given the code for the H^ COFF file. > H() executes H_Hat() in DebugTrace() mode From a high level perspective, we can say H calls DebugTrace() which returns an RC (return code) which is either zero or nonzero indicating its decision that the examined calculation either halts [RC != 0] or does not halt [RC=0]. What DebugTrace does internally matters to you (because you are writing it), but not so much at this high level (which should turn out to be enough to see your overall claim will not succeed). > The invocation of H() is in one process context, the first invocation of > H_Hat() is in another process context, and the second invocation of > H_Hat() is in the third process context. (OK, but those low level details are not the focus of my post) >> Can you confirm that in both the above execution paths, the >> DebugTrace(H_Hat, H_Hat) returns the same return code? > Yes. You have said "yes", but I'm not certain that we're communicating correctly. So far it seems to me you are only considering /one/ COFF file? (The H COFF file). Above, I mentioned execution contexts (or paths) and there are two of these that matter at the high level I am interested in. CONTEXT 1: In the *H* COFF file execution, DebugTrace(H_Hat,H_Hat) is called ONCE at the highest level (from main()). [If DebugTrace() internally results in further DebugTrace() invocations, at the high level I'm considering those don't matter...] CONTEXT 2: DebugTrace(H_Hat,H_Hat) is also called in the *H^* COFF file. It is called ONCE at the highest level, from H_Hat which in turn has just been called by main(). [Again, if DebugTrace() internally results in further DebugTrace() invocations, at the high level I'm considering those don't matter...] My question was whether /those/ two specific calls to DebugTrace returns the same RC. Mike. |
| Mike Terry <news.dead.person.stones@darjeeling.plus.com>: Oct 21 04:52PM +0100 On 21/10/2020 16:28, Mike Terry wrote: > returns an RC (return code) which is either zero or nonzero indicating > its decision that the examined calculation either halts [RC != 0] or > does not halt [RC=0]. Darn it! Despite trying to be careful it looks like I've still got the RCs the wrong way round :( DebugTrace RC=0: examined calculation terminates RC nonzero: examined calculation does not terminate |
| olcott <NoOne@NoWhere.com>: Oct 21 11:48AM -0500 On 10/21/2020 10:28 AM, Mike Terry wrote: > You have given the code for the H COFF file, and say there is no need > for any precompiler symbols, but you have not given the code for the H^ > COFF file. Because every function that is invoked by DebugTrace() is executed in its own separate process the source code that I provided specifies three separate virtual machines: (a) main() that executes H() (b) The H_Hat() that is executed by H() (c) The H_Hat() that is executed by itself. The most difficult aspect of this was to make sure that DebugTrace() could invoke itself recursively to an arbitrary depth. Each one of these invocations is in its own separate process. > What DebugTrace does internally matters to you (because you are writing > it), but not so much at this high level (which should turn out to be > enough to see your overall claim will not succeed). Yes I believe that is true. The key to this is noticing that the halting question has been changed: (a) Does H_Hat() halt on its input? (b) Does the execution of H_Hat() have to be aborted to prevent the halt decider from getting stuck in infinite execution? I have one more key element that can best be demonstrated by fully functional code. >> H_Hat() is in another process context, and the second invocation of >> H_Hat() is in the third process context. > (OK, but those low level details are not the focus of my post) Those low level details are only required to understand that the source code already specifies the execution of three separate virtual machines thus no need for any compile-time switch. > You have said "yes", but I'm not certain that we're communicating > correctly. So far it seems to me you are only considering /one/ COFF > file? (The H COFF file). As I have now fully elaborated the source file that I provided specifies x86utm executing main() which executes H() which invokes H_Hat() in its own separate process which invokes another H_Hat() in its own separate process. > called ONCE at the highest level (from main()). [If DebugTrace() > internally results in further DebugTrace() invocations, at the high > level I'm considering those don't matter...] A new and totally separate execution context is created every single time that DebugTrace() is invoked. > My question was whether /those/ two specific calls to DebugTrace returns > the same RC. > Mike. As Ben has very carefully elaborated twice the invocation of a function with the same input must result in the same output. The return value from H_Hat() and the return value from H() are the same return value. Like the Linz proof these "return values" are provided as halting in a final state. EAX = 0 means that the input program was aborted. EAX = 1 means that the input program terminated. -- Copyright 2020 Pete Olcott |
| Mike Terry <news.dead.person.stones@darjeeling.plus.com>: Oct 21 08:30PM +0100 On 21/10/2020 17:48, olcott wrote: > (a) main() that executes H() > (b) The H_Hat() that is executed by H() > (c) The H_Hat() that is executed by itself. Your claim is that you have two "TM-like-thingies" H and H^ where the two calculations H running with input (H^, H^) H^ running with input (H^) refute the Linz proof. In your paradigm TM-like-entities translates to COFF files (with an emulator providing the calculation side of things). So the /natural/ products you should deliver to support this are the two COFF files demonstrating the claimed behaviour. OK you're not going to do that, although it seems to me you /could/ do that, at the cost of just 10 minutes of extra effort, and then your delivery would logically match up with the claim you are making. Instead you are effectively saying, "I don't need to spend those 10 minutes, because in fact if you understood the internals of how I've implemented XXXXX you would see that the results that /would/ occur if I spent the extra 10 minutes can instead be /deduced/ by looking at particular subsets of the behaviour of the single COFF file. [Even though the code provided so far, does not even shows any call H_Hat (H_Hat).] I won't bother arguing with any of that, although it's a strange. > As Ben has very carefully elaborated twice the invocation of a function > with the same input must result in the same output. The return value > from H_Hat() and the return value from H() are the same return value. Hopefully this is a typo - I asked about return codes from DebugTrace, not from H or H_Hat. H^ in the Linz proof is not a decider of anything, so output from H^ is irrelevant; all that matters is whether it halts. I'll take it that you mean: "The calls to DebugTrace() in the two contexts you've described both return the same return code" (It being understood that when my contexts refer to two COFF files, you have equivalents in your single COFF file...) Yes, both Ben and I and others have all elaborated that this /should/ be the case, but I have to ask you, because it isn't clear to me that you would necessarily agree on this point. If you did agree, your claim would effectively be sunk, and you haven't withdrawn your claim of refuting the Linz proof. OK, so you say the calls to DebugTrace() in Context (1) and (2) return the same result. There are just two possibilities: *Both DebugTrace() RCs are zero* : In Context (1) this indicates that H will decide that calculation H_Hat (H_Hat) halts. (MOV_EAX_1; HALT; will be executed.) In Context (2) this means that the H_Hat code will take the branch containing HERE: goto HERE;, and so H_Hat will loop at this point. So H clearly made the wrong halt decision for the calculation. OK, so the other possibility is... *Both DebugTrace() RCs are non-zero* : In Context (1) this indicates that H will decide that calculation H_Hat (H_Hat) does not halt. (MOV_EAX_0; HALT; will be executed.) In Context (2) this means that the H_Hat code will take the branch containing MOV_EAX_0; HALT;, and so H_Hat(H_Hat) will halt at this point. Again H has made the wrong decision for the calculation. Those are the only possibilities! So your "TM"s agree in behaviour with the Linz proof. No refuting going on here! :) Mike. |
| olcott <NoOne@NoWhere.com>: Oct 21 03:27PM -0500 On 10/21/2020 2:30 PM, Mike Terry wrote: > H^ running with input (H^) > refute the Linz proof. > In your paradigm TM-like-entities translates to COFF files No you are wrong and have been corrected on this several times. >> with the same input must result in the same output. The return value >> from H_Hat() and the return value from H() are the same return value. > Hopefully this is a typo - I asked about return codes from DebugTrace, The return value from DebugTrace() is the same for H() and H_Hat(). > I'll take it that you mean: > "The calls to DebugTrace() in the two contexts you've > described both return the same return code" Yes. > have equivalents in your single COFF file...) > Yes, both Ben and I and others have all elaborated that this /should/ be > the case, No. Every software function having the same input can't possisbly have different output. > the branch containing MOV_EAX_0; HALT;, and so H_Hat(H_Hat) > will halt at this point. > Again H has made the wrong decision for the calculation. No you have this incorrectly. When I change the halting problem question: (a) Does H_Hat() halt on its input? (b) Does the execution of H_Hat() have to be aborted to prevent the halt decider from getting stuck in infinite execution? The previously undecidable halting problem becomes decidable. There are no longer any cases that are impossible to decide: (a) The input program must have its execution aborted. (b) The input program continues to execute until its execution terminates. -- Copyright 2020 Pete Olcott |
| "André G. Isaak" <agisaak@gm.invalid>: Oct 21 02:57PM -0600 On 2020-10-21 14:27, olcott wrote: > (b) Does the execution of H_Hat() have to be aborted to prevent the halt > decider from getting stuck in infinite execution? > The previously undecidable halting problem becomes decidable. When you change the halting problem question, then you are no longer addressing the halting problem. You are addressing some entirely different problem. > There are no longer any cases that are impossible to decide: > (a) The input program must have its execution aborted. Must have why? Because you got tired of waiting? How do you know it wouldn't have eventually halted on its own? I mean there may be cases where a given program is obviously stuck in an infinite loop (i.e. a very short loop), but there will also be cases where the program goes through a variety of states which don't end up repeating themselves until years or millennia into the future. André -- To email remove 'invalid' & replace 'gm' with well known Google mail service. |
| olcott <NoOne@NoWhere.com>: Oct 21 04:12PM -0500 On 10/21/2020 3:57 PM, André G. Isaak wrote: > When you change the halting problem question, then you are no longer > addressing the halting problem. You are addressing some entirely > different problem. Not when I change the question into an equlvalent question. >> (a) The input program must have its execution aborted. > Must have why? Because you got tired of waiting? How do you know it > wouldn't have eventually halted on its own? The halt decider examines its input program and decides that it would never halt. When it does this it reports that its input program was aborted. This is the exact same question as the orginal halting problem question except that this equivalent question is not subject to pathological self reference. It divides all of its inputs into halting and not halting. > where the program goes through a variety of states which don't end up > repeating themselves until years or millennia into the future. > André I have not made solving the halting problem easy. I merely refuted the proofs that show it is impossible. -- Copyright 2020 Pete Olcott |
| "André G. Isaak" <agisaak@gm.invalid>: Oct 21 03:54PM -0600 On 2020-10-21 15:12, olcott wrote: >> addressing the halting problem. You are addressing some entirely >> different problem. > Not when I change the question into an equlvalent question. If it really were the case that changing the question from (a) to (b) makes what was previously undecidable decidable, then obviously they cannot be equivalent questions. > The halt decider examines its input program and decides that it would > never halt. When it does this it reports that its input program was > aborted. And it decides this how? That sounds like a restatement of the halting problem that you purport to be solving, so the above is entirely uninformative. André -- To email remove 'invalid' & replace 'gm' with well known Google mail service. |
| Mike Terry <news.dead.person.stones@darjeeling.plus.com>: Oct 21 11:10PM +0100 On 21/10/2020 21:27, olcott wrote: >> On 21/10/2020 17:48, olcott wrote: >>> On 10/21/2020 10:28 AM, Mike Terry wrote: >>>> On 21/10/2020 04:07, olcott wrote: [... snip ...] >>>>> H(M, M); >>>>> HALT; >>>>> } [... snip ...] >> "The calls to DebugTrace() in the two contexts you've >> described both return the same return code" > Yes. [... snip ...] >> will halt at this point. >> Again H has made the wrong decision for the calculation. > No you have this incorrectly. You say that I have this incorrectly, without giving any indication of what you think is incorrect. That looks like being deliberately unhelpful! I'll have one more go - to save considering two alternatives for everything, which of the above possibilities will actually occur in the code you intend to finally deliver? Will both the DebugTrace() return codes be ZERO, or will they be NON-ZERO? (You previously agreed they would be the same...) Mike. |
| olcott <NoOne@NoWhere.com>: Oct 21 05:20PM -0500 On 10/21/2020 4:54 PM, André G. Isaak wrote: > problem that you purport to be solving, so the above is entirely > uninformative. > André Now that I have completed my x86utm operating system I finally have the required infrastructure to provide all the programming steps to decide whether or not H_Hat() must have its execution trace aborted because it would otherwise cause H() to be stuck in infinite execution or continue to DebugStep() H_Hat() until it completes its finite execution. The most difficult part of this was designing and implemented DebugTrace() so that it could DebugTrace() itself to an arbitrary recursive depth. All in all creating x86utm took about 2000 labor hours. The first 500 were wasted on trying to do everything from scratch. Even without providing anything more than I have already provided in this thread it should be able to be understood that the impossibility of solving the halting problem has been refuted by transforming the original question into an equivalent question that is not subject to pathological self-reference. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 21 05:55PM -0500 On 10/21/2020 5:10 PM, Mike Terry wrote: >> No you have this incorrectly. > You say that I have this incorrectly, without giving any indication of > what you think is incorrect. That looks like being deliberately unhelpful! Carefully study my words immediately below again and again until you fully understand exactly how I transformed a question subject to pathological self-reference into a question that is not subject to pathological self-reference thus eliminating the impossibility of solving the halting problem. -- 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