Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.software-eng > #1771 > unrolled thread

Halts() correctly decides the conventional counter-example of the HP proofs

Started byolcott <NoOne@NoWhere.com>
First post2020-11-20 12:11 -0600
Last post2020-11-20 18:34 -0600
Articles 7 — 2 participants

Back to article view | Back to comp.software-eng


Contents

  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

#1771 — Halts() correctly decides the conventional counter-example of the HP proofs

Fromolcott <NoOne@NoWhere.com>
Date2020-11-20 12:11 -0600
SubjectHalts() 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]


#1773

Fromolcott <NoOne@NoWhere.com>
Date2020-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]


#1775

Fromolcott <NoOne@NoWhere.com>
Date2020-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]


#1776

Fromolcott <NoOne@NoWhere.com>
Date2020-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]


#1779

Fromolcott <NoOne@NoWhere.com>
Date2020-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]


#1781

FromMr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date2020-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]


#1782

Fromolcott <NoOne@NoWhere.com>
Date2020-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