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


Groups > comp.theory > #25553

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

Newsgroups comp.theory, comp.ai.philosophy, comp.software-eng, comp.lang.c++
From olcott <NoOne@NoWhere.com>
Subject Halts() correctly decides the conventional counter-example of the HP proofs
Date 2020-11-20 12:11 -0600
Message-ID <LPWdnTsUnfB5myXCnZ2dnUU7-RfNnZ2d@giganews.com> (permalink)

Cross-posted to 4 groups.

Show all headers | View raw


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

Back to comp.theory | Previous | Next — Next in thread | Find similar | Unroll thread


Thread

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 Richard Damon <Richard@Damon-Family.org> - 2020-11-20 13:24 -0500
    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 Richard Damon <Richard@Damon-Family.org> - 2020-11-20 15:44 -0500
        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 Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-20 20:52 +0000
        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 Richard Damon <Richard@Damon-Family.org> - 2020-11-20 16:51 -0500
            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 Richard Damon <Richard@Damon-Family.org> - 2020-11-20 20:34 -0500
                Re: Halts() correctly decides the conventional counter-example of the HP proofs olcott <NoOne@NoWhere.com> - 2020-11-20 20:10 -0600
          Re: Halts() correctly decides the conventional counter-example of the HP proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-21 15:28 +0000
  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

csiph-web