Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #1771 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2020-11-20 12:11 -0600 |
| Last post | 2020-11-20 18:34 -0600 |
| Articles | 7 — 2 participants |
Back to article view | Back to comp.software-eng
Halts() correctly decides the conventional counter-example of the HP proofs olcott <NoOne@NoWhere.com> - 2020-11-20 12:11 -0600
Re: Halts() correctly decides the conventional counter-example of the HP proofs olcott <NoOne@NoWhere.com> - 2020-11-20 12:42 -0600
Re: Halts() correctly decides the conventional counter-example of the HP proofs olcott <NoOne@NoWhere.com> - 2020-11-20 15:14 -0600
Re: Halts() correctly decides the conventional counter-example of the HP proofs olcott <NoOne@NoWhere.com> - 2020-11-20 15:33 -0600
Re: Halts() correctly decides the conventional counter-example of the HP proofs olcott <NoOne@NoWhere.com> - 2020-11-20 16:07 -0600
Re: Halts() correctly decides the conventional counter-example of the HP proofs Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-11-21 00:05 +0000
Re: Halts() correctly decides the conventional counter-example of the HP proofs olcott <NoOne@NoWhere.com> - 2020-11-20 18:34 -0600
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-20 12:11 -0600 |
| Subject | Halts() correctly decides the conventional counter-example of the HP proofs |
| Message-ID | <LPWdnTsUnfB5myXCnZ2dnUU7-RfNnZ2d@giganews.com> |
When-so-ever decider Halts() (adapted from a UTM) decides that:
(a) its input (<P>,I) would never halt unless H stopped simulating it
and it is the case that
(b) its input (<P>,I) would never halt unless H stopped simulating it
then Halts() has made a correct not-halting decision on this input.
I just finished enough of the programming of my x86utm operating system
so that it collects the actual execution trace of every line of user
code that is executed. Of the 10,671 lines that are actually executed
only 35 lines are relevant to the halt decider's halting decision. All
of these lines are shown below.
Anyone with a bachelors degree in computer science would understand that
every Turing machine that has infinite recursion would never stop
running. That I show exactly how to decide the previously undecidable
input: (H_Hat shown below) proves that I have refuted all of the
conventional halting problem proofs.
My system is based on the x86 language that is known to be
computationally equivalent to a universal Turing machine for every
computation that does not require more memory than it has available:
x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company.
void H_Hat(u32 P)
{
u32 Aborted = Halts(P, P);
if (Aborted)
HALT
else
HERE: goto HERE;
}
int main()
{
u32 P = (u32)H_Hat;
Halts(P, P);
HALT;
}
_H_Hat()
[000004f7](01) 55 push ebp
[000004f8](02) 8bec mov ebp,esp
[000004fa](01) 51 push ecx
[000004fb](03) 8b4508 mov eax,[ebp+08]
[000004fe](01) 50 push eax
[000004ff](03) 8b4d08 mov ecx,[ebp+08]
[00000502](01) 51 push ecx
[00000503](05) e86ffeffff call 00000377
[00000508](03) 83c408 add esp,+08
[0000050b](03) 8945fc mov [ebp-04],eax
[0000050e](04) 837dfc00 cmp dword [ebp-04],+00
[00000512](02) 7403 jz 00000517
[00000514](01) f4 hlt
[00000515](02) eb02 jmp 00000519
[00000517](02) ebfe jmp 00000517
[00000519](02) 8be5 mov esp,ebp
[0000051b](01) 5d pop ebp
[0000051c](01) c3 ret
_main()
[00000527](01) 55 push ebp
[00000528](02) 8bec mov ebp,esp
[0000052a](01) 51 push ecx
[0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
[00000532](03) 8b45fc mov eax,[ebp-04]
[00000535](01) 50 push eax
[00000536](03) 8b4dfc mov ecx,[ebp-04]
[00000539](01) 51 push ecx
[0000053a](05) e838feffff call 00000377
[0000053f](03) 83c408 add esp,+08
[00000542](01) f4 hlt
[00000543](02) 8be5 mov esp,ebp
[00000545](01) 5d pop ebp
[00000546](01) c3 ret
Execution trace seen by the global halt decider
std_vector[00010abc]-->00000527 // main()
std_vector[00010ac0]-->00000528
std_vector[00010ac4]-->0000052a
std_vector[00010ac8]-->0000052b
std_vector[00010acc]-->00000532
std_vector[00010ad0]-->00000535
std_vector[00010ad4]-->00000536
std_vector[00010ad8]-->00000539
std_vector[00010adc]-->0000053a // call to _Halts()
std_vector[00010ae0]-->000004f7 // DebugStep(_H_Hat)
std_vector[00010ae4]-->000004f8
std_vector[00010ae8]-->000004fa
std_vector[00010aec]-->000004fb
std_vector[00010af0]-->000004fe
std_vector[00010af4]-->000004ff
std_vector[00010af8]-->00000502
std_vector[00010afc]-->00000503 // call to _Halts()
std_vector[00010b00]-->000004f7 // DebugStep(_H_Hat)
std_vector[00010b04]-->000004f8
std_vector[00010b08]-->000004fa
std_vector[00010b0c]-->000004fb
std_vector[00010b10]-->000004fe
std_vector[00010b14]-->000004ff
std_vector[00010b18]-->00000502
std_vector[00010b1c]-->00000503 // call to _Halts() infinite recursion
decided
Number of Instructions Executed(10671)
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-20 12:42 -0600 |
| Message-ID | <FoWdnVcOu_JlkCXCnZ2dnUU7-aXNnZ2d@giganews.com> |
| In reply to | #1771 |
On 11/20/2020 12:24 PM, Richard Damon wrote: > On 11/20/20 1:11 PM, olcott wrote: > >> Anyone with a bachelors degree in computer science would understand that >> every Turing machine that has infinite recursion would never stop >> running. That I show exactly how to decide the previously undecidable >> input: (H_Hat shown below) proves that I have refuted all of the >> conventional halting problem proofs. >> > The problem you have here is that H_Hat does NOT have inevitable > infinite recursion. You are right when-so-ever the decision made by Halts() has nothing to do with simulating H_Hat() in DebugStep() mode (For example Halts() makes a phone call to the psychic hotline) then H_Hat() is not inevitably infinitely recursive. In any case that whole line of reasoning does not matter. H.q0 wMw ⊢* H.qy H.q0 wMw ⊢* H.qn As long as I define anything at all for the ⊢* unspecified state transitions where wM and w are the Turing machine descriptions of Ĥ such that there is a transition to either H.qy or H.qn, then I have refuted the Linz proof. > The only reason you hit the infinite recuresion is > that you convert H(P, I) into a form of calling P(I). -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-20 15:14 -0600 |
| Message-ID | <J8KdnVOd3cY0rCXCnZ2dnUU7-YXNnZ2d@giganews.com> |
| In reply to | #1773 |
On 11/20/2020 2:44 PM, Richard Damon wrote: > On 11/20/20 1:42 PM, olcott wrote: >> On 11/20/2020 12:24 PM, Richard Damon wrote: >>> On 11/20/20 1:11 PM, olcott wrote: >>> >>>> Anyone with a bachelors degree in computer science would understand that >>>> every Turing machine that has infinite recursion would never stop >>>> running. That I show exactly how to decide the previously undecidable >>>> input: (H_Hat shown below) proves that I have refuted all of the >>>> conventional halting problem proofs. >>>> >>> The problem you have here is that H_Hat does NOT have inevitable >>> infinite recursion. >> >> You are right when-so-ever the decision made by Halts() has nothing to >> do with simulating H_Hat() in DebugStep() mode (For example Halts() >> makes a phone call to the psychic hotline) then H_Hat() is not >> inevitably infinitely recursive. >> >> In any case that whole line of reasoning does not matter. >> >> H.q0 wMw ⊢* H.qy >> H.q0 wMw ⊢* H.qn >> >> As long as I define anything at all for the ⊢* unspecified state >> transitions where wM and w are the Turing machine descriptions of Ĥ such >> that there is a transition to either H.qy or H.qn, then I have refuted >> the Linz proof. >> >>> The only reason you hit the infinite recuresion is >>> that you convert H(P, I) into a form of calling P(I). >> > > The question is NOT what you put into those states. The question is will > the machine H move from H.q0 to H.qx or H.qn in a finite number of H transitions from H.q0 to H.yes (halting) or H.no (not halting) > steps, and does the eventual state it ends up with match the behavior > that the actual machine whose representation it was given do when the > actual machine is actually run. When-so-ever decider H (adapted from a UTM) decides that: (a) its input (<P>,I) would never halt unless H stopped simulating it and it is the case that (b) its input (<P>,I) would never halt unless H stopped simulating it then H has made a correct not-halting decision on this input. Apparently you still do not fully understand that back cats are necessarily black and a decider that correctly decides not halting is a not-halting decider. > Note, that if there is some input which would cause H to loop within > itself forever, then the fault is in the behavior of H, not the input, > since the requirement on H is that is can handle ANY input tape. > > Your current proposed solution clearly fails this, and to a large part > because BECAUSE you did a bad mapping from the Turing Machine space to > the x86 von Neumann space, and lost the distinction between program and > input. > > You are claiming the issue is infinite recursion, but Turing Machines > allow for no such structure in the actual machine. (Yes, an Algorithm > can be infinitely recursive, but not a machine) This comes in part > because Turing Machines do NOT have the concept of a 'Subroutine', so > can not be in their structure truly recursive. Sure they do. I created this concept myself on the basis of conventional notions and terms. When a master UTM simulates the Turing Machine description of another UTM and this machine simulates the Turing Machine description itself we have the computational equivalanet of recursive function calls. > Looking at the form of the Turing Machine, it also becomes clear that > all the infinite executions you detected are actually issue with H, not > the program under test. Yes you can easily make that conclusion if you make sure to hardly pay any attention what-so-ever to what I am saying. On the other hand the execution trace that I provided conclusively proves otherwise. > Because you have worked hard at obfuscating the line between actual > machine and what is the Halt Detector processing the input, you have > tried to 'blame' the program for infinite execution which is actually > limitaitions in the Halt Detector to do its job in the presence of > Recursion. > The Halt Decider itself is a UTM that has been adapted to become a decider, it is not being simulated in any other UTM. Each of its programs under test are the Turing Machine descriptions of other machines. So the line-of-demarcation between the halt decider is essentially the same line-of-demarcation between a UTM and the machine that is is simulated. This is only difficult to see when one's primary goal is rebuttal and not mutual understanding. -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-20 15:33 -0600 |
| Message-ID | <0u-dnTap5JWnqyXCnZ2dnUU7-SvNnZ2d@giganews.com> |
| In reply to | #1773 |
On 11/20/2020 2:52 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> In any case that whole line of reasoning does not matter. >> >> H.q0 wMw ⊢* H.qy >> H.q0 wMw ⊢* H.qn > > Yeah! The notation you don't know how to use pops up again! > >> As long as I define anything at all for the ⊢* unspecified state >> transitions where wM and w are the Turing machine descriptions of Ĥ >> such that there is a transition to either H.qy or H.qn, then I have >> refuted the Linz proof. > > Nope. It's trivial to do what you say here, I did not bother to say it with complete precision. Richard Damon seems to think that when he defines a decider that has undecidable inputs that this is somehow a rebuttal to every other decider. No one here seems to understand that in order to prove that a decider has undecidable inputs one must provide a counter-example of an input that is undecidable. This aspect really is not rocket science, yet no one here seem to understand something as simple as this. - As long as I define anything at all for the ⊢* - unspecified state transitions where wM and w are - the Turing machine descriptions of Ĥ such that the transition to H.Yes indicates that the input has the property of halting and the state transition to H.No indicates that the input does not have the property of halting, then H has decided its input correctly. The following is true by logical necessity: When-so-ever decider H (adapted from a UTM) decides that: (a) its input (<P>,I) would never halt unless H stopped simulating it and it is the case that (b) its input (<P>,I) would never halt unless H stopped simulating it then H has made a correct not-halting decision on this input. Thus when the above criteria decides that H_Hat would not halt it is impossibly incorrect. > for example if H's δ > includes ((H.q0, s), (H.qy, s, R)) for every s ∈ Γ. It refutes nothing. > Can you see what you are getting wrong? > > (Aside, Linz's subscript notation and narrow spacing are a mess in this > format. [M] w is much clearer than wMw. In your case the tape contents > are [Ĥ] [Ĥ].) > -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-20 16:07 -0600 |
| Message-ID | <y9ednUkMDLW0oyXCnZ2dnUU7-anNnZ2d@giganews.com> |
| In reply to | #1776 |
On 11/20/2020 3:51 PM, Richard Damon wrote: > On 11/20/20 4:33 PM, olcott wrote: >> On 11/20/2020 2:52 PM, Ben Bacarisse wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> In any case that whole line of reasoning does not matter. >>>> >>>> H.q0 wMw ⊢* H.qy >>>> H.q0 wMw ⊢* H.qn >>> >>> Yeah! The notation you don't know how to use pops up again! >>> >>>> As long as I define anything at all for the ⊢* unspecified state >>>> transitions where wM and w are the Turing machine descriptions of Ĥ >>>> such that there is a transition to either H.qy or H.qn, then I have >>>> refuted the Linz proof. >>> >>> Nope. It's trivial to do what you say here, >> >> I did not bother to say it with complete precision. >> >> Richard Damon seems to think that when he defines a decider that has >> undecidable inputs that this is somehow a rebuttal to every other decider. > > BULLSHIT. > > I have been saying that your decider FAILS TO DECIDER CORRECTLY a given > input. You already acknowledged that this decision critera is impossibly incorrect: When-so-ever decider H (adapted from a UTM) decides that: (a) its input (<P>,I) would never halt unless H stopped simulating it and it is the case that (b) its input (<P>,I) would never halt unless H stopped simulating it then H has made a correct not-halting decision on this input. > That IS proof that your given decider is not a correct universal decider. Although you and others may continue to disagree that I am correct what all have you have utterly failed to do is provide even a single-counter example that the decider decides incorrectly. > Linz has proved that there can be no such decider anywhere, and YOU are Bullshit. He proved no such thing. TRY AND FIND ONE COUNTER EXAMPLE THAT THIS DECIDES INCORRECTLY: When-so-ever decider H (adapted from a UTM) decides that: (a) its input (<P>,I) would never halt unless H stopped simulating it and it is the case that (b) its input (<P>,I) would never halt unless H stopped simulating it then H has made a correct not-halting decision on this input. FAIL TO DO THAT AND EVERYONE WILL KNOW WHO HAS FAILED. -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> |
|---|---|
| Date | 2020-11-21 00:05 +0000 |
| Message-ID | <cRYtH.63557$b5kb.24714@fx15.ams4> |
| In reply to | #1771 |
On 20/11/2020 18:11, olcott wrote: > When-so-ever decider Halts() (adapted from a UTM) decides that: > (a) its input (<P>,I) would never halt unless H stopped simulating it > and it is the case that > (b) its input (<P>,I) would never halt unless H stopped simulating it > then Halts() has made a correct not-halting decision on this input. > > I just finished enough of the programming of my x86utm operating system so that it collects the actual execution trace of every line of user code that is executed. Of the 10,671 lines that are actually executed only 35 lines are relevant to the halt decider's halting decision. All of these lines are shown below. > > Anyone with a bachelors degree in computer science would understand that every Turing machine that has infinite recursion would never stop running. That I show exactly how to decide the previously undecidable input: (H_Hat shown below) proves that I have refuted all of the conventional halting problem proofs. 1) Infinite recursion isn't the only cause of non-halting behaviour; 2) If your solution is based on finite RAM and register state being repeated then you are not testing a UTM as your so-called "UTM" is not an arbitrary TM nor is it acting on arbitrary input. Still nothing to see here. /Flibble -- ¬
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-20 18:34 -0600 |
| Message-ID | <VLOdnT0lScHl_SXCnZ2dnUU7-QvNnZ2d@giganews.com> |
| In reply to | #1781 |
On 11/20/2020 6:05 PM, Mr Flibble wrote: > On 20/11/2020 18:11, olcott wrote: >> When-so-ever decider Halts() (adapted from a UTM) decides that: >> (a) its input (<P>,I) would never halt unless H stopped simulating it >> and it is the case that >> (b) its input (<P>,I) would never halt unless H stopped simulating it >> then Halts() has made a correct not-halting decision on this input. >> >> I just finished enough of the programming of my x86utm operating >> system so that it collects the actual execution trace of every line of >> user code that is executed. Of the 10,671 lines that are actually >> executed only 35 lines are relevant to the halt decider's halting >> decision. All of these lines are shown below. >> >> Anyone with a bachelors degree in computer science would understand >> that every Turing machine that has infinite recursion would never stop >> running. That I show exactly how to decide the previously undecidable >> input: (H_Hat shown below) proves that I have refuted all of the >> conventional halting problem proofs. > > 1) Infinite recursion isn't the only cause of non-halting behaviour; You are correct, yet in the case at hand H_Hat() would never halt unless the halt decider stops simulating it. > 2) If your solution is based on finite RAM and register state being > repeated then you are not testing a UTM as your so-called "UTM" is not > an arbitrary TM nor is it acting on arbitrary input. x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine None-the-less the equivalence between computations under my x86utm operating system and those of an actual UTM continues to exist for all computations not requiring more memory than is available. The conventional halting problem counter-example embodied by H_Hat() is such a computation. > Still nothing to see here. > > /Flibble > -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [standalone]
Back to top | Article view | comp.software-eng
csiph-web