| olcott <NoOne@NoWhere.com>: May 06 11:03AM -0500 On 5/6/2021 10:52 AM, André G. Isaak wrote: > fundamentally different proofs (they're not, but I did say 'imagine'), > and Linz's H_Hat and Sipser's D are constructed in entirely different > manners. Page 4 indicates exactly how all three proofs are related by a key element. http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf > That you *think* you've found a way of defeating Sipser's D has no > bearing on the halting problem when there are other proofs which your > approach can't deal with. And you can't deal with Linz. Linz H decides not halting on Linz Ĥ on the basis of infinitely nested simulation: http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf For every at least partial halt decider H that bases its halting decision on simulating its input unless H decides infinitely nested simulation (not halting), stops simulating Ĥ(Ĥ), and decides not halting the alternative is that H never returns and Ĥ remains in infinitely nested simulation. This proves that my concept is sound even on the original Linz proof. The correct answer is infinitely nested simulation (not halting), only the path to arrive at this correct answer varies. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: May 05 05:48PM -0700 On 5/5/2021 7:52 AM, olcott wrote: >>> H_Hat((u32)H_Hat) halts? >> One suggestion... use a proper function pointer? > I have to force everything to be 32 bits. Does your simulator force this? How does it handle simulating C code that uses function pointers? |
| olcott <NoOne@NoWhere.com>: May 05 08:09PM -0500 On 5/5/2021 7:48 PM, Chris M. Thomasson wrote: >> I have to force everything to be 32 bits. > Does your simulator force this? How does it handle simulating C code > that uses function pointers? I created the x86utm operating system so that the halting problem could be explored using the much higher level languages of C and x86. http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf 32-bit function pointers are generally cast into unsigned 32-bit integers to more closely correspond to an actual Turing machine. Most anything that can be written 32-bit in C can probably be executed in x86utm because the x86 emulator is quite robust. The one thing that is excluded is linked libraries. The x86utm operating system directly executes COFF object files that have not been linked to libraries. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: May 05 06:27PM -0700 On 5/5/2021 6:09 PM, olcott wrote: > in x86utm because the x86 emulator is quite robust. The one thing that > is excluded is linked libraries. The x86utm operating system directly > executes COFF object files that have not been linked to libraries. Iirc, you mentioned that you did not create the simulator/emulator? Right? What one are you using? |
| Tim Woodall <news001@woodall.me.uk>: May 06 09:47AM >> I have to force everything to be 32 bits. > Does your simulator force this? How does it handle simulating C code > that uses function pointers? This is crazy. If everything is 32 bits (including memory being bounded by 32 bit addressing) then the halting problem for that subset of programs is trivially[1] decidable on a 64 bit machine as the step function is computable. [1] Where trivially means it will take a lot longer than the lifetime of the universe to decide for some programs but it will decide eventually. |
| Juha Nieminen <nospam@thanks.invalid>: May 06 12:18PM > by 32 bit addressing) > then the halting problem for that subset of programs is trivially[1] > decidable on a 64 bit machine as the step function is computable. Rather obviously if the machine can only be in a finite number of different states, the problem is trivial: Simply check if a previous state has been reached or not. Of course such a solution is quite useless because it doesn't tell us much. The reason for this is that, for example, any binary "yes / no" problem actually becomes a trinary problem: "Yes / no / out of memory". All the interesting problems would fall into that last category, thus making it useless. (Even if some problem could be solved in the finite amount of space, they may take too long to check.) > [1] Where trivially means it will take a lot longer than the lifetime of > the universe to decide for some programs but it will decide eventually. I don't think "the lifetime of the universe" begins to even scratch the surface. I think a computer with an address space of just a few hundreds of bytes would take longer than the age of the universe to go through every possible state. |
| Tim Woodall <news001@woodall.me.uk>: May 06 12:45PM > Rather obviously if the machine can only be in a finite number of different > states, the problem is trivial: Simply check if a previous state has been > reached or not. You don't even need to do that. Just calculate an upper bound of how many steps it takes until the program either MUST have repeated or terminated and then run the program for that number of steps (or until it terminates). If it doesn't terminate then you know it never terminates as it is looping (you don't know how many steps in the loop but you don't care). That's why S(n) has to be non-computable in general. https://en.wikipedia.org/wiki/Busy_beaver#Proof_for_uncomputability_of_S(n)_and_%CE%A3(n) (and the known lower bound for S(7) tells you why it's a false errand even thinking you can "disprove" the halting problem using a (simulation of a) 32 bit machine.) |
| olcott <NoOne@NoWhere.com>: May 06 09:16AM -0500 On 5/6/2021 4:47 AM, Tim Woodall wrote: > decidable on a 64 bit machine as the step function is computable. > [1] Where trivially means it will take a lot longer than the lifetime of > the universe to decide for some programs but it will decide eventually. Linz H decides not halting on Linz Ĥ on the basis of infinite recursion. http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| olcott <NoOne@NoWhere.com>: May 06 09:17AM -0500 On 5/6/2021 7:18 AM, Juha Nieminen wrote: > surface. I think a computer with an address space of just a few > hundreds of bytes would take longer than the age of the universe to go > through every possible state. Good point -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| olcott <NoOne@NoWhere.com>: May 06 10:52AM -0500 On 5/6/2021 10:26 AM, Ben Bacarisse wrote: > No. In order to save time (yours and mine), I've said I'll ask if you'd > like to learn this material before taking the time to explain. Do say > if you have time to learn why this is wrong. More literally for every at least partial halt decider H that bases its halting decision on simulating its input unless H decides infinitely nested simulation (not halting), stops simulating Ĥ(Ĥ), and decides not halting the alternative is that H never returns and Ĥ remains in infinitely nested simulation. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| 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