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


Groups > comp.lang.c++ > #79388 > unrolled thread

Solution To The Halting Problem

Started byMr Flibble <flibble@i42.REMOVETHISBIT.co.uk>
First post2021-05-02 14:15 +0100
Last post2021-05-14 11:12 -0500
Articles 20 on this page of 47 — 12 participants

Back to article view | Back to comp.lang.c++


Contents

  Solution To The Halting Problem Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2021-05-02 14:15 +0100
    Re: Solution To The Halting Problem Kaz Kylheku <563-365-8930@kylheku.com> - 2021-05-02 14:03 +0000
      Re: Solution To The Halting Problem Richard Harnden <richard.nospam@gmail.com> - 2021-05-02 15:15 +0100
        Re: Solution To The Halting Problem [ C/x86 defines computable functions ] olcott <NoOne@NoWhere.com> - 2021-05-04 19:41 -0500
          Re: Solution To The Halting Problem [ C/x86 defines computable functions ] Kaz Kylheku <563-365-8930@kylheku.com> - 2021-05-05 00:55 +0000
      Re: Solution To The Halting Problem Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-02 16:59 +0200
      Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-02 10:30 -0500
        Re: Solution To The Halting Problem [ Accurate Review? ] Real Troll <real.troll@trolls.com> - 2021-05-02 17:01 +0100
          Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-02 12:21 -0500
            Re: Solution To The Halting Problem [ Accurate Review? ] wij <wyniijj@gmail.com> - 2021-05-02 12:04 -0700
              Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-02 15:08 -0500
                Re: Solution To The Halting Problem [ Accurate Review? ] Christian Gollwitzer <auriocus@gmx.de> - 2021-05-07 18:01 +0200
                  Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-07 13:15 -0500
                  Re: Solution To The Halting Problem [ Accurate Review? ] Tim Woodall <news001@woodall.me.uk> - 2021-05-07 20:33 +0000
                    Re: Solution To The Halting Problem [ Accurate Review? ] Christian Gollwitzer <auriocus@gmx.de> - 2021-05-07 22:54 +0200
                    OT: decision problems Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-07 23:35 +0100
            Re: Solution To The Halting Problem [ Accurate Review? ] "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-04 22:50 -0700
              Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-05 09:52 -0500
                Re: Solution To The Halting Problem [ Accurate Review? ] "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-05 17:48 -0700
                  Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-05 20:09 -0500
                    Re: Solution To The Halting Problem [ Accurate Review? ] "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-05 18:27 -0700
                      Re: Solution To The Halting Problem [ Accurate Review? ] "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-07 00:34 -0700
                      Re: Solution To The Halting Problem [ Accurate Review? ] "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-16 15:08 -0700
                  Re: Solution To The Halting Problem [ Accurate Review? ] Tim Woodall <news001@woodall.me.uk> - 2021-05-06 09:47 +0000
                    Re: Solution To The Halting Problem [ Accurate Review? ] Juha Nieminen <nospam@thanks.invalid> - 2021-05-06 12:18 +0000
                      Re: Solution To The Halting Problem [ Accurate Review? ] Tim Woodall <news001@woodall.me.uk> - 2021-05-06 12:45 +0000
                      Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-06 09:17 -0500
                    Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-06 09:16 -0500
                      Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-06 10:52 -0500
                        Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-07 09:14 -0500
    Re: Solution To The Halting Problem Real Troll <real.troll@trolls.com> - 2021-05-02 16:20 +0100
    Re: Solution To The Halting Problem [ H based on UTM ]( correct answer ) olcott <NoOne@NoWhere.com> - 2021-05-06 11:03 -0500
      Re: New test program (succeeds) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-05-07 18:38 +0000
      Re: New test program (Succeeds V2) olcott <NoOne@NoWhere.com> - 2021-05-07 16:13 -0500
        Re: New test program (Succeeds V2)(Ben contradicts himself) olcott <NoOne@NoWhere.com> - 2021-05-08 11:18 -0500
        Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) olcott <NoOne@NoWhere.com> - 2021-05-08 17:45 -0500
          Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) wij <wyniijj@gmail.com> - 2021-05-08 19:21 -0700
            Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) olcott <NoOne@NoWhere.com> - 2021-05-08 21:35 -0500
              Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) wij <wyniijj@gmail.com> - 2021-05-08 20:02 -0700
                Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) olcott <NoOne@NoWhere.com> - 2021-05-08 22:11 -0500
                  Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) wij <wyniijj@gmail.com> - 2021-05-08 20:55 -0700
                    Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) olcott <NoOne@NoWhere.com> - 2021-05-08 23:07 -0500
                      Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2021-05-09 19:18 +0100
                      Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) wij <wyniijj@gmail.com> - 2021-05-09 12:15 -0700
          Re: New test program (Succeeds V2)[ Mike is a good technical reviewer ] olcott <NoOne@NoWhere.com> - 2021-05-10 14:36 -0500
    Re: New test program (Succeeds V2)[ counter-example in C ? ] olcott <NoOne@NoWhere.com> - 2021-05-12 15:45 -0500
      Re: New test program (Succeeds V2)[ entirely different computation ] olcott <NoOne@NoWhere.com> - 2021-05-14 11:12 -0500

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →


#79425 — Re: Solution To The Halting Problem [ Accurate Review? ]

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2021-05-05 18:27 -0700
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<s6vglm$1t1$1@gioia.aioe.org>
In reply to#79424
On 5/5/2021 6:09 PM, olcott wrote:
> On 5/5/2021 7:48 PM, Chris M. Thomasson wrote:
>> On 5/5/2021 7:52 AM, olcott wrote:
>>> On 5/5/2021 12:50 AM, Chris M. Thomasson wrote:
>>>> On 5/2/2021 10:21 AM, olcott wrote:
>>>>> On 5/2/2021 11:01 AM, Real Troll wrote:
>>>>>>
>>>>>>> I am going to continue to post until an accurate review proves 
>>>>>>> that I a right or proves that I am wrong.
>>>>>>
>>>>>>
>>>>>> Don't be sure about that because people will get fed up of you and 
>>>>>> write to your NewsServer provider:
>>>>>>
>>>>>> <
>>>>>> abuse@giganews.com
>>>>>>>
>>>>>>
>>>>>> So be very careful before you test people's tolerance threshold here.
>>>>>>
>>>>>
>>>>> Since all of my posts have the analysis of "C" code as their 
>>>>> primary focus, none of my posts can be reasonably construed as off 
>>>>> topic for C or C++ groups.
>>>>>
>>>>> This is the "C" code that is the primary focus of all of my posts:
>>>>>
>>>>> void H_Hat(u32 P)
>>>>> {
>>>>>    u32 Input_Halts = Halts(P, P);
>>>>>    if (Input_Halts)
>>>>>      HERE: goto HERE;
>>>>> }
>>>>>
>>>>> int main() {
>>>>>    u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
>>>>>    Output("Input_Would_Halt = ", Input_Would_Halt);
>>>>> }
>>>>>
>>>>> Can a C/C++ function be defined that correctly decides whether or 
>>>>> not 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?
> 
> 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.
> 

Iirc, you mentioned that you did not create the simulator/emulator? 
Right? What one are you using?

[toc] | [prev] | [next] | [standalone]


#79436 — Re: Solution To The Halting Problem [ Accurate Review? ]

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2021-05-07 00:34 -0700
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<s72qhf$n6k$1@gioia.aioe.org>
In reply to#79425
On 5/5/2021 6:27 PM, Chris M. Thomasson wrote:
> On 5/5/2021 6:09 PM, olcott wrote:
>> On 5/5/2021 7:48 PM, Chris M. Thomasson wrote:
>>> On 5/5/2021 7:52 AM, olcott wrote:
>>>> On 5/5/2021 12:50 AM, Chris M. Thomasson wrote:
>>>>> On 5/2/2021 10:21 AM, olcott wrote:
>>>>>> On 5/2/2021 11:01 AM, Real Troll wrote:
>>>>>>>
>>>>>>>> I am going to continue to post until an accurate review proves 
>>>>>>>> that I a right or proves that I am wrong.
>>>>>>>
>>>>>>>
>>>>>>> Don't be sure about that because people will get fed up of you 
>>>>>>> and write to your NewsServer provider:
>>>>>>>
>>>>>>> <
>>>>>>> abuse@giganews.com
>>>>>>>>
>>>>>>>
>>>>>>> So be very careful before you test people's tolerance threshold 
>>>>>>> here.
>>>>>>>
>>>>>>
>>>>>> Since all of my posts have the analysis of "C" code as their 
>>>>>> primary focus, none of my posts can be reasonably construed as off 
>>>>>> topic for C or C++ groups.
>>>>>>
>>>>>> This is the "C" code that is the primary focus of all of my posts:
>>>>>>
>>>>>> void H_Hat(u32 P)
>>>>>> {
>>>>>>    u32 Input_Halts = Halts(P, P);
>>>>>>    if (Input_Halts)
>>>>>>      HERE: goto HERE;
>>>>>> }
>>>>>>
>>>>>> int main() {
>>>>>>    u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
>>>>>>    Output("Input_Would_Halt = ", Input_Would_Halt);
>>>>>> }
>>>>>>
>>>>>> Can a C/C++ function be defined that correctly decides whether or 
>>>>>> not 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?
>>
>> 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.
>>
> 
> Iirc, you mentioned that you did not create the simulator/emulator? 
> Right? What one are you using?

Don't be afraid. Its okay. For instance, I have C/C++ code that 
generates files that a wonderful program called PovRay can read. I 
create a shit load of files and PovRay reads and renders them. I did 
that to create the following animation. My C/C++ can be used as a 
generator, then PovRay can read the results and render the damn thing!

https://youtu.be/skGUAXAx6eg

So, My work was in C++ for this. The ray tracer was in PovRay:

http://www.povray.org

Its  a text format, easy...

[toc] | [prev] | [next] | [standalone]


#79511 — Re: Solution To The Halting Problem [ Accurate Review? ]

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2021-05-16 15:08 -0700
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<s7s55d$7tq$1@gioia.aioe.org>
In reply to#79425
On 5/5/2021 6:27 PM, Chris M. Thomasson wrote:
> On 5/5/2021 6:09 PM, olcott wrote:
>> On 5/5/2021 7:48 PM, Chris M. Thomasson wrote:
>>> On 5/5/2021 7:52 AM, olcott wrote:
>>>> On 5/5/2021 12:50 AM, Chris M. Thomasson wrote:
>>>>> On 5/2/2021 10:21 AM, olcott wrote:
>>>>>> On 5/2/2021 11:01 AM, Real Troll wrote:
>>>>>>>
>>>>>>>> I am going to continue to post until an accurate review proves 
>>>>>>>> that I a right or proves that I am wrong.
>>>>>>>
>>>>>>>
>>>>>>> Don't be sure about that because people will get fed up of you 
>>>>>>> and write to your NewsServer provider:
>>>>>>>
>>>>>>> <
>>>>>>> abuse@giganews.com
>>>>>>>>
>>>>>>>
>>>>>>> So be very careful before you test people's tolerance threshold 
>>>>>>> here.
>>>>>>>
>>>>>>
>>>>>> Since all of my posts have the analysis of "C" code as their 
>>>>>> primary focus, none of my posts can be reasonably construed as off 
>>>>>> topic for C or C++ groups.
>>>>>>
>>>>>> This is the "C" code that is the primary focus of all of my posts:
>>>>>>
>>>>>> void H_Hat(u32 P)
>>>>>> {
>>>>>>    u32 Input_Halts = Halts(P, P);
>>>>>>    if (Input_Halts)
>>>>>>      HERE: goto HERE;
>>>>>> }
>>>>>>
>>>>>> int main() {
>>>>>>    u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
>>>>>>    Output("Input_Would_Halt = ", Input_Would_Halt);
>>>>>> }
>>>>>>
>>>>>> Can a C/C++ function be defined that correctly decides whether or 
>>>>>> not 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?
>>
>> 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.
>>
> 
> Iirc, you mentioned that you did not create the simulator/emulator? 
> Right? What one are you using?

What simulator are you using?

[toc] | [prev] | [next] | [standalone]


#79426 — Re: Solution To The Halting Problem [ Accurate Review? ]

FromTim Woodall <news001@woodall.me.uk>
Date2021-05-06 09:47 +0000
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<s70e01$fak$2@einstein.home.woodall.me.uk>
In reply to#79423
On 2021-05-06, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
> On 5/5/2021 7:52 AM, olcott 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?

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.

[toc] | [prev] | [next] | [standalone]


#79427 — Re: Solution To The Halting Problem [ Accurate Review? ]

FromJuha Nieminen <nospam@thanks.invalid>
Date2021-05-06 12:18 +0000
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<s70mr0$1pln$1@gioia.aioe.org>
In reply to#79426
In comp.lang.c++ Tim Woodall <news001@woodall.me.uk> wrote:
> On 2021-05-06, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>> On 5/5/2021 7:52 AM, olcott 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?
> 
> 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.

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.

[toc] | [prev] | [next] | [standalone]


#79428 — Re: Solution To The Halting Problem [ Accurate Review? ]

FromTim Woodall <news001@woodall.me.uk>
Date2021-05-06 12:45 +0000
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<s70oe1$a23$1@einstein.home.woodall.me.uk>
In reply to#79427
On 2021-05-06, Juha Nieminen <nospam@thanks.invalid> wrote:
> In comp.lang.c++ Tim Woodall <news001@woodall.me.uk> wrote:
>> On 2021-05-06, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>> On 5/5/2021 7:52 AM, olcott 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?
>> 
>> 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.
>
> 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.)

[toc] | [prev] | [next] | [standalone]


#79430 — Re: Solution To The Halting Problem [ Accurate Review? ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-06 09:17 -0500
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<odOdnaMCyqLDZw79nZ2dnUU7-Q2dnZ2d@giganews.com>
In reply to#79427
On 5/6/2021 7:18 AM, Juha Nieminen wrote:
> In comp.lang.c++ Tim Woodall <news001@woodall.me.uk> wrote:
>> On 2021-05-06, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>>> On 5/5/2021 7:52 AM, olcott 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?
>>
>> 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.
> 
> 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.
> 

Good point

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#79429 — Re: Solution To The Halting Problem [ Accurate Review? ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-06 09:16 -0500
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<odOdnaACyqKzZw79nZ2dnUU7-Q3NnZ2d@giganews.com>
In reply to#79426
On 5/6/2021 4:47 AM, Tim Woodall wrote:
> On 2021-05-06, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>> On 5/5/2021 7:52 AM, olcott 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?
> 
> 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.
> 

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

[toc] | [prev] | [next] | [standalone]


#79431 — Re: Solution To The Halting Problem [ Accurate Review? ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-06 10:52 -0500
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<3pSdnapwgcYOjQn9nZ2dnUU7-KvNnZ2d@giganews.com>
In reply to#79429
On 5/6/2021 10:26 AM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> Linz H decides not halting on Linz Ĥ on the basis of infinite recursion.
>> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
> 
> 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

[toc] | [prev] | [next] | [standalone]


#79441 — Re: Solution To The Halting Problem [ Accurate Review? ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-07 09:14 -0500
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<zcSdnW7DLI-B1gj9nZ2dnUU7-UvNnZ2d@giganews.com>
In reply to#79431
On 5/7/2021 8:25 AM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 5/6/2021 7:47 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/6/2021 6:39 PM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 5/6/2021 5:53 PM, Ben Bacarisse wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 5/6/2021 4:22 PM, Ben Bacarisse wrote:
>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 5/6/2021 10:26 AM, Ben Bacarisse wrote:
>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> Linz H decides not halting on Linz Ĥ on the basis of infinite recursion.
>>>>>>>>>>>> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>>>>>>>>>>>
>>>>>>>>>>> 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.
>>>>>>>>>
>>>>>>>>> Well that saves me some time.  You don't want to know why you were wrong
>>>>>>>>> in the previous post.
>>>>>>>>
>>>>>>>> You can say that I am wrong and this has as much actual truth behind
>>>>>>>> is as Trump won the election by a unanimous consensus.
>>>>>>>>
>>>>>>>> Any dishonest lout can falsely claim that someone is wrong.
>>>>>>>
>>>>>>> Yes.  And someone knowledgeable a truthful like me could tell you what
>>>>>>> you got wrong, but you told me you don't have time for that, so I won't
>>>>>>> unless you ask me to.  And I'm only offering to do that for the first
>>>>>>> mistake above.
>>>>>>
>>>>>> _Infinite_Loop()...
>>>>>
>>>>> I am offering to explain one thing: why "Linz H decides not halting on
>>>>> Linz Ĥ on the basis of infinite recursion" is wrong but you keep
>>>>> ignoring this offer.  Either ask me to explain (and take the trouble to
>>>>> read what then write) or leave the thread alone.
>>>>>
>>>>
>>>> Try and refute this more accurately stated basis:
>>>>
>>>> Ĥ.q0  wM  ⊢*  Ĥ.qx  wM  wM  ⊢*  Ĥ.qy  ∞
>>>> Ĥ.q0  wM  ⊢*  Ĥ.qx  wM  wM  ⊢*  Ĥ.qn
>>>>
>>>> The above is adapted from (Linz:1990:319).
>>>> It shows that Turing machine Ĥ copies its input at (q0) and begins
>>>> executing an embedded copy of the original halt decider with this
>>>> input at (qx).
>>>
>>> I like your use of . to identify the TM a state belongs to, but you
>>> never use it to its full potential.  Instead of having to say what qx
>>> is, you could write H.q0.
>>
>> That would be incorrect.
>> The code from H that is now embedded within Ĥ is no longer H.
> 
> You can call the states of H^ anything you like.  Using H.s for those
> copied from H just helps talk about them
> 
>>> And you could show the H'.qa and H'.qb states
>>> rather the describing them in words.
>>
>> It is no longer H' states. The whole thing is now a single contiguous
>> Ĥ
> 
> Then there is no point in using the dot.  It just gets in the way.
> 
>>>> It can be understood from the above specification that when the
>>>> embedded halt decider @Ĥ.qx bases its halting decision on simulating
>>>> its input, and it has (Ĥ,  Ĥ) as its input that:
>>>
>>>> Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with this copy then
>>>> Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with this copy then
>>>> Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with this copy...
>>>> unless and until the halt decider @Ĥ.qx stops simulating its input.
>>>
>>> Yes.  I wonder why you think this is in doubt.
>>
>> It means that the halting problem instance is decidable as not
>> halting.
> 
> No.  Explanation available on request.
> 
>>>> Linz, Peter 1990. An Introduction to Formal Languages and
>>>> Automata. Lexington/Toronto: D. C. Heath and Company.
>>>
>>> Take care here.  This makes it look like Linz wrote the silly stuff
>>> about simulation.  He didn't.
>>>
>>> Does this mean you /would/ like me to say why "Linz H decides not halting
>>> on Linz Ĥ on the basis of infinite recursion" is wrong?  Maybe you can
>>> see it for yourself now?
>>
>> As I said infinite recursion is not precisely correct it is actually
>> infinitely nested simulation.
> 
> So you don't want your original mistake explained?  OK.  Why not just
> say "no", rather than blather?
> 
>> You just agreed that for every at least partial halt decider H that is
>> based on simulating its input that Ĥ(Ĥ) does specify infinitely nested
>> simulation unless H stops simulating it.
> 
> The nested simulations are finite in number.  What /would/ happen unless
> something or other were done is irrelevant.  What matters is what /is/
> done, and the nested simulations are stopped and are therefore not
> infinite.
> 
>> So what is left that you could possibly say is incorrect:
> 
> The same as ever: that Halts(H_Hat, H_Hat) is false when the arguments
> denote a finite computation.  I.e. that it gives the wrong answer.  You
> can't get round this with words.
> 

void Infinite_Loop()
{
   HERE: goto HERE;
}

int main()
{
   Halts(Infinite_Loop(), Infinite_Loop());
}

How is it that you are not making the mistake of calling Infinite_Loop() 
a finite computation because its simulation was stopped?

That would be like called a dead cow alive on the basis that it moves 
when the rendering plant workers pick up its corpse.

> Also incorrect is that you reject one or other or both of these:
> 
> (A1) For every instance of the halting problem that represents a finite
> computation, the correct answer is "yes".
> (A2) For every instance of the halting problem that does not represent
> a finite computation, the correct answer is "no".
> 
> You keep trying to make the wrong answer sound reasonable, but even if
> you could, you are not saying anything about the halting problem because
> I tell /you/ what the right answers are for that problem.
> 

If you are saying that infinite loops are not infinite then what you are 
saying makes much less sense than what I am saying and others will know 
this and agree.

> Your not-the-halting-problem is, none the less, interesting because, in
> general, it too is undecidable, but you don't know that yet.
> 

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#79392

FromReal Troll <real.troll@trolls.com>
Date2021-05-02 16:20 +0100
Message-ID<s6mg9p$g1$2@gioia.aioe.org>
In reply to#79388
On 02/05/2021 14:15, Mr Flibble wrote:
> Does anyone know the solution to the problem of halting olcott's 
> Usenet posts?
>
> /Flibble
>
Killfile should work for you. Try it.

I am surprised you are asking this because you like trolls here. I have seen you are responding to that religious nutter on every post he writes about his saviour Mr Christ.


[toc] | [prev] | [next] | [standalone]


#79432 — Re: Solution To The Halting Problem [ H based on UTM ]( correct answer )

Fromolcott <NoOne@NoWhere.com>
Date2021-05-06 11:03 -0500
SubjectRe: Solution To The Halting Problem [ H based on UTM ]( correct answer )
Message-ID<JO6dneVy4Nu4jgn9nZ2dnUU7-WnNnZ2d@giganews.com>
In reply to#79388
On 5/6/2021 10:52 AM, André G. Isaak wrote:
> On 2021-05-05 22:03, olcott wrote:
>> On 5/5/2021 10:45 PM, André G. Isaak wrote:
> 
> <snippage>
> 
>>> The problem here is that your Halts(H_Hat, H_Hat) doesn't meet the 
>>> above specification, at least not if we take your claims about how 
>>> this works seriously.
>>>
>>
>> Whether or not the current code meets the above specification (I 
>> believe that it does) the above specification does provide the 
>> criterion measure to determine infinitely nested simulation, stop this 
>> simulation on this basis and report non-halting.
>>
>>> You have Halts() simulating H_Hat, which in turn calls Halts(), but 
>>> that latter halts isn't going to be at the same machine address 
>>
>> As a matter of objective fact it <is> at the same address and that it 
>> is at the same address is the way that the same code can serve 
>> multiple clients. In the bad old days of the internet code was 
>> duplicated to serve multiple clients.
> 
> Then you're using the term 'simulation' in a very unorthodox manner...
> 
> But let's put that aside for the moment. You justify the fact that H_Hat 
> calls the *same* version of Halts() as the outermost halt on the grounds 
> that you are doing this 'The Sipser Way'.
> 
> Let's imagine, just for sake of argument, that your interpretation of 
> Sipser is actually correct, and that Sipser *doesn't* embed a copy of 
> Halts within his D.
> 
> That would mean that the Sipser proof and the Linz proof are 
> 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

> But from the outset you claimed your goal was to 'disprove' the 
> 'conventional halting proofs'. Now I have no idea how you decide which 
> proofs are conventional and which are not, or why only the 
> 'conventional' proofs matter, but if you had actually found some fatal 
> flaw in Sipser's proof, that wouldn't magically make the Linz proof go 
> away.
> 
> You still need to show how your 'decider' manages to correctly decide 
> Linz's H_Hat, where a *copy* of H is embedded in H_Hat. If you can't do 
> that, Linz's proof still stands, and your 'recursion pattern' which is 
> based on comparing addresses is *not* going to work for Linz's H_Hat.
> 
> 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.

>>> as the outer halts since it is part of the simulation. Similarly, 
>>> subsequent calls to halts will be to simulations of simulations of 
>>> Halts(), and so forth.
>>>
>>> You can't meaningfully compare machine addresses from an actual call 
>>> and a simulation of that call, or a simulation [...] of a simulation 
>>> of that call.
>>>
>>> Moreover, there *are* conditional branches between calls to each 
>>> successive level of simulation since your 'decider' needs to 
>>> determine whether to abort a given simulation. That's going to 
>>> involve a conditional.
>>>
>>> André
>>>
>>
>> There are conditional branches in the halt decider when the halt 
>> decider decides that the above infinite loop would never halt, 
>> none-the-less its decision is correct. The key basis is whether or not 
>> the infinite 
> 
> But then you're not following the pattern which you claim to be 
> following since you are ignoring some conditional branches. How do you 
> decide which conditional branches are ignorable and which are not?
> 
> André
> 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#79446 — Re: New test program (succeeds)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-05-07 18:38 +0000
SubjectRe: New test program (succeeds)
Message-ID<20210507110743.697@kylheku.com>
In reply to#79432
["Followup-To:" header set to comp.theory.]
On 2021-05-07, olcott <NoOne@NoWhere.com> wrote:
> On 5/6/2021 6:53 PM, Kaz Kylheku wrote:
>> On 2021-05-06, olcott <NoOne@NoWhere.com> wrote:
>>> On 5/6/2021 4:31 PM, Kaz Kylheku wrote:
>>>> On 2021-05-06, olcott <NoOne@NoWhere.com> wrote:
>>>>> I don't have nothing. I have the correct return value for H(Ĥ, Ĥ).
>>>>> I also have a method for deciding a computationally equivalent instance.
>>>>
>>>> Can you prove that your Halts always returns the same answer for
>>>> the same parameters, as required?
>>> It is your mistake that this is required.
>>>
>>> When-so-ever Halts() is called in the equivalent of infinite recursion
>>> it can't possibly return anything until after it terminates this
>>> infinite simulation nesting.
>> 
>> Sorry, yes, right; I forgot something important in the pseudo code! My
>> apologies.
>> 
>> Please use this one. (It is the same as the previous, except for
>> differences in the main function):
>> 
>> Please integrate this, and provide execution trace. Thx!
>> 
>>    #define NRES 4
>> 
>>    // Cached results from calling Halts
>> 
>>    struct HaltResult {
>>      U32 P, I, H;
>>    } res[4];
>> 
>>    // Wrapper for calling Halts.
>> 
>>    U32 HaltsProxy(U32 P, U32 I)
>>    {
>>      int i;
>>      U32 H = Halts(P, I); // call real Halts
>> 
>>      for (i = 0; i < NRES; i++) {
>>        struct HaltResult *r = &res[i];
>> 
>>        if (r->P == 0 && r->I == 0 && r->H == 0) {
>>          // Blank spot in array: enter result here
>>          r->P = P;
>>          r->I = I;
>>          r->H = H;
>>          break;
>>        } else if (r->P == P && r->I == I) {
>>          // Repeat call for same P, I.
>> 
>>          if (r->H != H) {
>>            // Halts has returned a different value
>>            Output("Halt decider is not an algorithm!");
>>            loop0: goto loop0;
>>          }
>> 
>>          // Same value; we are done checking.
>>          break;
>>        }
>> 
>>        if (i >= NRES) {
>>          // Array has filled up, what? We only call this twice.
>>          Output("Unexpected excess calls to HaltsProxy!");
>>          loop1: goto loop1;
>>        }
>>      }
>> 
>>      return H;
>>    }
>> 
>>    void H_Hat(u32 P)
>>    {
>>      if (HaltsProxy(P, P)) {
>>      loop: goto loop;
>>      }
>>    }
>> 
>>    int main(void)
>>    {
>>      U32 H = HaltsProxy((u32) H_hat, (u32) H_Hat);
>>      Output("Input halts = ", H);
>>      H_Hat((u32) H_Hat);
>>      Output("Halt returned");
>>      return 0;
>>    }
>> 
>
> Below is the corrrected source code, assembly language and complete 
> exuection trace.
>
>
> #define NRES 4
>
> struct HaltResult
> {
>     u32 P, I, H;
> };
>
> struct HaltResult res[4] = {{1,1,1},{2,2,2},{3,3,3},{4,4,4}};

I don't understand the purpose of this initializer, given
that Init_res is called.

If omission of the initializer is sufficient for zero initialization
(as normally required by ISO C for a static object) please remove it.

Otherwise use res[NRES] = {{0}};

By the way [4] is my mistake; it was intended to be [NRES]. NRES is 4,
but could change, causing a problem.


> void H_Hat(u32 P)
> {
>    if (HaltsProxy(P, P))
>      loop: goto loop;
> }
>
> void Init_res()
> {
>    u32 P = (u32)H_Hat, I = (u32)H_Hat;
>    u32 H = Halts(P, I);
>    for (u32 N = 0; N < NRES; N++)
>    {
>      res[N].P = P;
>      res[N].I = I;
>      res[N].H = H;
>    }
> }

This doesn't make a whole lot of sense. The initialization has no need
to call Halts at all; that should be left to the experiment.

We want the database to be initially empty, not having any knowledge
about any halts results.

Filling the array with *identical* keys makes no sense, and leaves no
room for any other P, I value should that happen.

> u32 HaltsProxy(u32 P, u32 I)
> {
>    int i;
>    u32 H = Halts(P, I); // call real Halts
>    for (i = 0; i < NRES; i++)
>    {
>      struct HaltResult *r = &res[i];
>
>      if (r->P == P && r->I == I)
>      {
>        // Repeat call for same P, I.
>        H = Halts(P, I); // call real Halts

Calling Halts(P, I) more than once in this function does not make sense.

Halts(P, I) was already called at the top, and H holds the result.
Please delete this call to Halts.

>        if (r->H != H)
>        {
>          // Halts has returned a different value
>          OutputString("Halt decider is not an algorithm!");
>          loop0: goto loop0;
>        }
>          // Same value; we are done checking.
>          break;
>      }

>      if (i >= NRES)

This statement was originally outside of the loop.

The condition i >= NRES indicates that the loop completed without a
"break". That means that (P, I) was not found in the array, and that the
array contains no more blank space toc reate a new entry for the newly
observed (P, I) value.

NOte that testing (i >= NRES) inside the for loop makes no
sense,  because the loop guard assures that the condition is always
false:  for (i = 0; i < NRES; i++).  See the "i < NRES"? The loop body
does not execute unless i < NRES< therefore i >= NRES is false inside
the loop body.

You've turned a piece of my code that serves a purpose into unreachable
code.

Also, please restore the logic which adds new entries into blank spots in
the array.

      {
>        // Array has filled up, what? We only call this twice.
>        OutputString("Unexpected excess calls to HaltsProxy!");
>        loop1: goto loop1;
>      }
>    }
>    return H;
> }

In spite of these problems, I think it look as if the the code should
still catch the situation of Halts being inconsistent.
>
> int main()
> {
>    Init_res();
>    u32 H = HaltsProxy((u32) H_Hat, (u32) H_Hat);
>    Output("Input halts = ", H);
>    H_Hat((u32) H_Hat);
>    OutputString("Halt returned");

My mistake: please correct to H_Hat returned.

>    return 0;
> }

OK, so onto the trace. In the trace we see:

> Input halts = 0

thus Halts(H_Hat, H_Hat) returned 0 when called out of main via
HaltsProxy.

In the trace we also see this output:

> Halt returned

This actually means H_Hat returned, the code being

    H_Hat((u32) H_Hat);
    OutputString("Halt returned");

Since "Input_Halts = 0" means "H_Hat(H_Hat) does not halt", but
H_Hat(H_Hat) returns, that means it's the wrong halting answer,
doesn't it?

So while we didn't see an inconsistent return value from Halts (which is
good!) the program's behavior appears to support the halting proof,
rather than refute it.

Of course if Halts(H_Hat, H_Hat) consistently returns 0, that
consistency being required, then H_Hat(H_Hat) returns. It obtains the
that 0 from Halts and "behaves opposite" by just returning, making that
the wrong answer.

I specifically did not miss these two pieces of output in your trace:

> Begin Local Halt Decider Simulation at Machine Address:bf5

Firstly, you had previously claimed that the local decider mode was
a mistake and have abandoned it; does Local Halt Decider not refer
to this mode, or is that something else now.

And, more importantly:

> Local Halt Decider: Infinite Recursion Detected Simulation Stopped

Though it claims it has detected infinite recursion and that the simulation has
stopped, the fact is that the traces continue after this diagnostic. The
simuation has not actually stopped!

Moreover, the claim of infinite recursion is difficult to accept given that:

1. Halts((u32) H_Hat, (u32) H_Hat) cheerfully terminated with value 0.

2. H_Hat((u32) H_Hat) returned to subsequent Output statement

I understand you have some talking points around all this, but they don't make
sense, especially in relation to the simplicity of arriving at the conclusion
that the apparatus is simply confirming the proof.

-- 
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

[toc] | [prev] | [next] | [standalone]


#79449 — Re: New test program (Succeeds V2)

Fromolcott <NoOne@NoWhere.com>
Date2021-05-07 16:13 -0500
SubjectRe: New test program (Succeeds V2)
Message-ID<aeOdnQfkqKIdMAj9nZ2dnUU7-SvNnZ2d@giganews.com>
In reply to#79432
On 5/7/2021 3:37 PM, Kaz Kylheku wrote:
> On 2021-05-07, olcott <NoOne@NoWhere.com> wrote:
>> #define NRES 4
>>
>> struct HaltResult
>> {
>>      u32 P, I, H;
>> };
>>
>> struct HaltResult res[4] = {{1,1,1},{2,2,2},{3,3,3},{4,4,4}};
> 
> It would be good if you would pick up the res[NRES] fix here,
> as well as Output("H_Hat returned") in main.
> 
>>
>> void Init_res()
>> {
>>     for (u32 N = 0; N < NRES; N++)
>>     {
>>       res[N].P = 0;
>>       res[N].I = 0;
>>       res[N].H = 0;
>>     }
>> }
> 
> Yes, this initialization now meets the intent of the original code.
> 
> I think that for the longer term, it would be good to repair your COFF
> loader so that it handles the zero-initialized data which is indicated
> in the COFF file.
> 
> Then you can explore whatever C code you want without workarounds
> for zero-initialized statics.
> 

Yes as soon as my halt decider is accepted as correct this is first on 
the list of enhacements.

>>       if (i >= NRES)
>>       {
>>         // Array has filled up, what? We only call this twice.
>>         OutputString("Unexpected excess calls to HaltsProxy!");
>>         loop1: goto loop1;
>>       }
> 
> Nitpick: that should still be restored to its position outside of the
> loop. We never run into this condition either way, since we don't work
> with multiple unique P, I pairs.
> 

I only corrected syntax errors in your code.
Your code stipulates that it is inside the loop.

You probably got confused by your formatting conventions. I always match 
curly braces on a line by themselves with the same indentation level.

> Otherwise you might as well remove this code; it is unreachable.
> 
>>     }
>>     return H;
>> }
>>

It is not unreachable.

>>
>> void H_Hat4(u32 P)
> 
> Seeing you use different names for different H_Hat versions is
> encouraging.
> 

Good.

>> int TestHaltsProxy()
>> {
>>     Init_res();
>>     u32 H = HaltsProxy((u32) H_Hat4, (u32) H_Hat4);
>>     Output("Input halts = ", H);
>>     H_Hat4((u32) H_Hat4);
>>     OutputString("Halt returned");
> 
> Please correct to "H_Hat4 returned"; that was my intent.
> 

OK

> Your execution trace is essentially the same as before.
> 
> The issue is that we see these, in that order:
> 
>> Begin Local Halt Decider Simulation at Machine Address:d45
> 
> (Halts starts running a nested simulated machine executing H_Hat4(H_Hat4)).
> 
>> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
>> ...[00000c88][0010192e][90909090](03)  83c408                  add esp,+08
>> ...[00000c8b][0010192e][00000000](03)  8945f4                  mov
> 
> (outer simulation continues)
> 
>> Input halts = 0
> 
> (Halts has returned 0 to main.)
> 
>> Begin Local Halt Decider Simulation at Machine Address:d45
> 
> (another nested simulation: this is due to H_Hat4(H_Hat4) calling Halts!)
> 
>> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
> 
> (stops again, but surrounding simulation keeps going)
> 
>> Halt returned
> 
> Oops, H_Hat4(H_Hat4) returns due to getting getting a 0 from Halts.
> 
> So the 0 is incorrect: a direct call to H_Hat4(H_Hat4) returns.
> 

Halts(H_Hat, H_Hat) is an instance of both of these truisms:

It is true that every computation that would never halt unless its 
simulation was stopped is a non-halting computation. Some may disagree 
out of ignorance or deception none-the-less it remains a truism.

Every at least partial halt decider that decides to stop simulating its 
input on the basis that the execution trace of this input matches a 
correct non-halting behavior pattern does decide not halting correctly.

Do you understand that disagreeing with an actual truism is always 
necessarily incorrect?

> The "Input halts = 0" result has exactly the meaning that "a direct call
> to H_Hat4(H_Hat4) out of main shall not terminate". Yet that's exactly
> what that call does.
> 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#79458 — Re: New test program (Succeeds V2)(Ben contradicts himself)

Fromolcott <NoOne@NoWhere.com>
Date2021-05-08 11:18 -0500
SubjectRe: New test program (Succeeds V2)(Ben contradicts himself)
Message-ID<UradnZAeOaBHJAv9nZ2dnUU7-S_NnZ2d@giganews.com>
In reply to#79449
On 5/7/2021 9:12 PM, Ben Bacarisse wrote:
> Richard Damon <Richard@Damon-Family.org> writes:
> 
>> What intuitition is needed. You posted a trace of H_Hat(H_Hat) and it
>> shows that H_Hat(H_Hat) came to a halt.
>>
>> What is your response to that?
> 
> I think we finally know:
> 
>    "the fact that a computation halts does not entail that it is a halting
>    computation"  Peter Olcott, May 2021.
> 
> Presumably that fact that H_Hat(H_Hat) halts does not entail that
> H_Hat(H_Hat) is a halting computation, so you can answer "no" if the
> mood takes you.

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
 > A computation that would not halt if its simulation were not
 > halted is indeed a non-halting computation. But a computation that
 > would not halt and one that is halted are different computations.

It is true that every computation that would never halt unless its 
simulation was stopped is a non-halting computation.

As is shown by the following example computations meeting this criteria 
remain non-halting even after they are forced to halt by their halt 
deciding simulator thus contradicting Ben's second sentence.

_Infinite_Loop()
[00000aaf](01)  55                      push ebp
[00000ab0](02)  8bec                    mov ebp,esp
[00000ab2](02)  ebfe                    jmp 00000ab2
[00000ab4](01)  5d                      pop ebp
[00000ab5](01)  c3                      ret
Size in bytes:(0007) [00000ab5]

// (a) The instruction is a JMP instruction.
// (b) It is jumping upward or to its own address.
// (c) There are no conditional branch instructions inbetween.
// (d) There are no other JMP instructions inbetween (André G. Isaak)

When we apply the above criteria to the above code a program can 
definitively decide that it would not halt. When the above code is 
simulated its execution trace indicates that it would not halt because 
its behavior matches the above criteria.

This remains true even after _Infinite_Loop() is forced to halt because 
the halt deciding simulator stopped simulating it. Thus Ben's first 
sentence is correct and his second sentence is incorrect because it 
contradicts his first sentence.

THIS IS A TRUISM:
It is true that every computation that would never halt unless its 
simulation was stopped is a non-halting computation.

The fact that an {infinite loop, infinite recursion, infinitely nested 
simulation) was forced to halt when its halt deciding simulator decided 
that its behavior matched a pattern of non-halting behavior and stopped 
simulating it is the exceptional case where:

On 5/7/2021 9:12 PM, Ben Bacarisse wrote:
 >    "the fact that a computation halts does not entail that
 >     it is a halting computation"  Peter Olcott, May 2021.



-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#79465 — Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not )

Fromolcott <NoOne@NoWhere.com>
Date2021-05-08 17:45 -0500
SubjectRe: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not )
Message-ID<-8OdnY5xf4EViQr9nZ2dnUU7-ffNnZ2d@giganews.com>
In reply to#79449
On 5/8/2021 5:06 PM, Kaz Kylheku wrote:
> On 2021-05-08, olcott <NoOne@NoWhere.com> wrote:
>> On 5/8/2021 3:24 PM, Kaz Kylheku wrote:
>>> On 2021-05-08, olcott <NoOne@NoWhere.com> wrote:
>>>> Dishonest people are free to disagree with verified facts, honest people
>>>> are not.
>>>
>>> Yes; verified facts like uncomputability of halting, Gödel's
>>> incompleteness theorems and such.
>>>
>>
>> Removing this key context seems quite dishonest:
>>
>> On 5/8/2021 10:57 AM, Kaz Kylheku wrote:
>>> There is no evidence that H_Hat is forced to stop.
>>
>> I will not assume that dishonesty was your intention.
>>
>>>> The following execution trace proves that the input H_Hat()
>>>> <is> forced to stop at its machine address [00000b67].
>>>
>>> Your execution traces don't prove anything because they omit
>>> reams and reams of instructions.
>>
>> It does prove that H_Hat was forced to stop.
> 
> Your own traces shows that H_Hat resumes. Here is one of them,
> abridged:
> 

In the following I show every single detail of exactly how the 
non-halting behavior pattern of infinite recursion or infinitely nested 
simulation has been matched by Halts((u32)H_Hat, (u32)H_Hat).

The the only possible way that non-halting has been decided incorrectly 
is an error in the criteria shown below.


When an execution trace matches the following criteria we know that the 
non-halting behavior of infinite recursion or infinitely nested 
simulation has been matched:

If the execution trace of function Y() shows:
    (1)  function X() is called twice in sequence from the same machine 
address of Y()
    (2)  with the same parameters to X()
    (3)  with no conditional branch or indexed jump instructions in Y()
    (4)  with no function call returns from X()
then the function call from Y() to X() is infinitely recursive.

void H_Hat(u32 P)
{
   u32 Input_Halts = Halts(P, P);
   if (Input_Halts)
     HERE: goto HERE;
}

int main()
{
   u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
   Output("Input_Would_Halt = ", Input_Would_Halt);
}

_H_Hat()
[00000b1f](01)  55                      push ebp
[00000b20](02)  8bec                    mov ebp,esp
[00000b22](01)  51                      push ecx
[00000b23](03)  8b4508                  mov eax,[ebp+08]
[00000b26](01)  50                      push eax
[00000b27](03)  8b4d08                  mov ecx,[ebp+08]
[00000b2a](01)  51                      push ecx
[00000b2b](05)  e82ffeffff              call 0000095f
[00000b30](03)  83c408                  add esp,+08
[00000b33](03)  8945fc                  mov [ebp-04],eax
[00000b36](04)  837dfc00                cmp dword [ebp-04],+00
[00000b3a](02)  7402                    jz 00000b3e
[00000b3c](02)  ebfe                    jmp 00000b3c
[00000b3e](02)  8be5                    mov esp,ebp
[00000b40](01)  5d                      pop ebp
[00000b41](01)  c3                      ret
Size in bytes:(0035) [00000b41]

_main()
[00000b4f](01)  55                      push ebp
[00000b50](02)  8bec                    mov ebp,esp
[00000b52](01)  51                      push ecx
[00000b53](05)  681f0b0000              push 00000b1f
[00000b58](05)  681f0b0000              push 00000b1f
[00000b5d](05)  e8fdfdffff              call 0000095f
[00000b62](03)  83c408                  add esp,+08
[00000b65](03)  8945fc                  mov [ebp-04],eax
[00000b68](03)  8b45fc                  mov eax,[ebp-04]
[00000b6b](01)  50                      push eax
[00000b6c](05)  682b030000              push 0000032b
[00000b71](05)  e8e9f7ffff              call 0000035f
[00000b76](03)  83c408                  add esp,+08
[00000b79](02)  33c0                    xor eax,eax
[00000b7b](02)  8be5                    mov esp,ebp
[00000b7d](01)  5d                      pop ebp
[00000b7e](01)  c3                      ret
Size in bytes:(0048) [00000b7e]

Columns
(1) Machine address of instruction
(2) Machine address of top of stack
(3) Value of top of stack after instruction executed
(4) Number of bytes of machine code
(5) Machine language bytes
(6) Assembly language text

...[00000b4f][00101542][00000000](01)  55              push ebp
...[00000b50][00101542][00000000](02)  8bec            mov ebp,esp
...[00000b52][0010153e][00000000](01)  51              push ecx
...[00000b53][0010153a][00000b1f](05)  681f0b0000      push 00000b1f
...[00000b58][00101536][00000b1f](05)  681f0b0000      push 00000b1f
...[00000b5d][00101532][00000b62](05)  e8fdfdffff      call 0000095f

Begin Local Halt Decider Simulation at Machine Address:b1f
...[00000b1f][002115e2][002115e6](01)  55              push ebp
...[00000b20][002115e2][002115e6](02)  8bec            mov ebp,esp
...[00000b22][002115de][002015b2](01)  51              push ecx
...[00000b23][002115de][002015b2](03)  8b4508          mov eax,[ebp+08]
...[00000b26][002115da][00000b1f](01)  50              push eax
...[00000b27][002115da][00000b1f](03)  8b4d08          mov ecx,[ebp+08]
...[00000b2a][002115d6][00000b1f](01)  51              push ecx
...[00000b2b][002115d2][00000b30](05)  e82ffeffff      call 0000095f
The above eight instructions repeat

...[00000b1f][0025c00a][0025c00e](01)  55              push ebp
...[00000b20][0025c00a][0025c00e](02)  8bec            mov ebp,esp
...[00000b22][0025c006][0024bfda](01)  51              push ecx
...[00000b23][0025c006][0024bfda](03)  8b4508          mov eax,[ebp+08]
...[00000b26][0025c002][00000b1f](01)  50              push eax
...[00000b27][0025c002][00000b1f](03)  8b4d08          mov ecx,[ebp+08]
...[00000b2a][0025bffe][00000b1f](01)  51              push ecx
...[00000b2b][0025bffa][00000b30](05)  e82ffeffff      call 0000095f
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
Infinite recursion / Infinitely nested simulation criteria has been met

(1) function X() is called twice in sequence from the same machine 
address of Y()
...[00000b2b][002115d2][00000b30](05)  e82ffeffff      call 0000095f

(2) with the same parameters to X()
The pair of push instructions preceding call 0000095f push the value of 
0xb1f (The address of H_Hat) onto the stack as input to Halts().

(3) with no conditional branch or indexed jump instructions in Y()
No instructions between 0xb1f and 0xb2b of H_Hat() fit this category.

(4) with no function call returns from X()
Halts() is a simulator that never returns to its input.

...[00000b62][0010153e][00000000](03)  83c408                  add esp,+08
...[00000b65][0010153e][00000000](03)  8945fc                  mov 
[ebp-04],eax
...[00000b68][0010153e][00000000](03)  8b45fc                  mov 
eax,[ebp-04]
...[00000b6b][0010153a][00000000](01)  50                      push eax
...[00000b6c][00101536][0000032b](05)  682b030000              push 0000032b
...[00000b71][00101532][00000b76](05)  e8e9f7ffff              call 0000035f
Input_Would_Halt = 0
...[00000b76][0010153e][00000000](03)  83c408                  add esp,+08
...[00000b79][0010153e][00000000](02)  33c0                    xor eax,eax
...[00000b7b][00101542][00000000](02)  8be5                    mov esp,ebp
...[00000b7d][00101546][00100000](01)  5d                      pop ebp
...[00000b7e][0010154a][00000080](01)  c3                      ret
Number_of_User_Instructions(33)
Number of Instructions Executed(26560)

I also updated this file with these clarifications:
http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf



-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#79466 — Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not )

Fromwij <wyniijj@gmail.com>
Date2021-05-08 19:21 -0700
SubjectRe: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not )
Message-ID<1e2844ea-46c2-4774-8c35-2703e78bfe2dn@googlegroups.com>
In reply to#79465
On Sunday, 9 May 2021 at 06:45:48 UTC+8, olcott wrote:
> On 5/8/2021 5:06 PM, Kaz Kylheku wrote: 
> > On 2021-05-08, olcott <No...@NoWhere.com> wrote: 
> >> On 5/8/2021 3:24 PM, Kaz Kylheku wrote: 
> >>> On 2021-05-08, olcott <No...@NoWhere.com> wrote: 
> >>>> Dishonest people are free to disagree with verified facts, honest people 
> >>>> are not. 
> >>> 
> >>> Yes; verified facts like uncomputability of halting, Gödel's 
> >>> incompleteness theorems and such. 
> >>> 
> >> 
> >> Removing this key context seems quite dishonest: 
> >> 
> >> On 5/8/2021 10:57 AM, Kaz Kylheku wrote: 
> >>> There is no evidence that H_Hat is forced to stop. 
> >> 
> >> I will not assume that dishonesty was your intention. 
> >> 
> >>>> The following execution trace proves that the input H_Hat() 
> >>>> <is> forced to stop at its machine address [00000b67]. 
> >>> 
> >>> Your execution traces don't prove anything because they omit 
> >>> reams and reams of instructions. 
> >> 
> >> It does prove that H_Hat was forced to stop. 
> > 
> > Your own traces shows that H_Hat resumes. Here is one of them, 
> > abridged: 
> > 
> 
> In the following I show every single detail of exactly how the 
> non-halting behavior pattern of infinite recursion or infinitely nested 
> simulation has been matched by Halts((u32)H_Hat, (u32)H_Hat). 
> 
> The the only possible way that non-halting has been decided incorrectly 
> is an error in the criteria shown below. 
> 
> 
> When an execution trace matches the following criteria we know that the 
> non-halting behavior of infinite recursion or infinitely nested 
> simulation has been matched: 
> 
> If the execution trace of function Y() shows: 
> (1) function X() is called twice in sequence from the same machine 
> address of Y() 
> (2) with the same parameters to X() 
> (3) with no conditional branch or indexed jump instructions in Y() 
> (4) with no function call returns from X() 
> then the function call from Y() to X() is infinitely recursive. 
> 
> void H_Hat(u32 P) 
> { 
> u32 Input_Halts = Halts(P, P); 
> if (Input_Halts) 
> HERE: goto HERE; 
> } 
> 
> int main() 
> { 
> u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat); 
> Output("Input_Would_Halt = ", Input_Would_Halt); 
> } 
> 
> _H_Hat() 
> [00000b1f](01) 55 push ebp 
> [00000b20](02) 8bec mov ebp,esp 
> [00000b22](01) 51 push ecx 
> [00000b23](03) 8b4508 mov eax,[ebp+08] 
> [00000b26](01) 50 push eax 
> [00000b27](03) 8b4d08 mov ecx,[ebp+08] 
> [00000b2a](01) 51 push ecx 
> [00000b2b](05) e82ffeffff call 0000095f 
> [00000b30](03) 83c408 add esp,+08 
> [00000b33](03) 8945fc mov [ebp-04],eax 
> [00000b36](04) 837dfc00 cmp dword [ebp-04],+00 
> [00000b3a](02) 7402 jz 00000b3e 
> [00000b3c](02) ebfe jmp 00000b3c 
> [00000b3e](02) 8be5 mov esp,ebp 
> [00000b40](01) 5d pop ebp 
> [00000b41](01) c3 ret 
> Size in bytes:(0035) [00000b41] 
> 
> _main() 
> [00000b4f](01) 55 push ebp 
> [00000b50](02) 8bec mov ebp,esp 
> [00000b52](01) 51 push ecx 
> [00000b53](05) 681f0b0000 push 00000b1f 
> [00000b58](05) 681f0b0000 push 00000b1f 
> [00000b5d](05) e8fdfdffff call 0000095f 
> [00000b62](03) 83c408 add esp,+08 
> [00000b65](03) 8945fc mov [ebp-04],eax 
> [00000b68](03) 8b45fc mov eax,[ebp-04] 
> [00000b6b](01) 50 push eax 
> [00000b6c](05) 682b030000 push 0000032b 
> [00000b71](05) e8e9f7ffff call 0000035f 
> [00000b76](03) 83c408 add esp,+08 
> [00000b79](02) 33c0 xor eax,eax 
> [00000b7b](02) 8be5 mov esp,ebp 
> [00000b7d](01) 5d pop ebp 
> [00000b7e](01) c3 ret 
> Size in bytes:(0048) [00000b7e] 
> 
> Columns 
> (1) Machine address of instruction 
> (2) Machine address of top of stack 
> (3) Value of top of stack after instruction executed 
> (4) Number of bytes of machine code 
> (5) Machine language bytes 
> (6) Assembly language text 
> 
> ...[00000b4f][00101542][00000000](01) 55 push ebp 
> ...[00000b50][00101542][00000000](02) 8bec mov ebp,esp 
> ...[00000b52][0010153e][00000000](01) 51 push ecx 
> ...[00000b53][0010153a][00000b1f](05) 681f0b0000 push 00000b1f 
> ...[00000b58][00101536][00000b1f](05) 681f0b0000 push 00000b1f 
> ...[00000b5d][00101532][00000b62](05) e8fdfdffff call 0000095f 
> 
> Begin Local Halt Decider Simulation at Machine Address:b1f 
> ...[00000b1f][002115e2][002115e6](01) 55 push ebp 
> ...[00000b20][002115e2][002115e6](02) 8bec mov ebp,esp 
> ...[00000b22][002115de][002015b2](01) 51 push ecx 
> ...[00000b23][002115de][002015b2](03) 8b4508 mov eax,[ebp+08] 
> ...[00000b26][002115da][00000b1f](01) 50 push eax 
> ...[00000b27][002115da][00000b1f](03) 8b4d08 mov ecx,[ebp+08] 
> ...[00000b2a][002115d6][00000b1f](01) 51 push ecx 
> ...[00000b2b][002115d2][00000b30](05) e82ffeffff call 0000095f 
> The above eight instructions repeat 
> 
> ...[00000b1f][0025c00a][0025c00e](01) 55 push ebp 
> ...[00000b20][0025c00a][0025c00e](02) 8bec mov ebp,esp 
> ...[00000b22][0025c006][0024bfda](01) 51 push ecx 
> ...[00000b23][0025c006][0024bfda](03) 8b4508 mov eax,[ebp+08] 
> ...[00000b26][0025c002][00000b1f](01) 50 push eax 
> ...[00000b27][0025c002][00000b1f](03) 8b4d08 mov ecx,[ebp+08] 
> ...[00000b2a][0025bffe][00000b1f](01) 51 push ecx 
> ...[00000b2b][0025bffa][00000b30](05) e82ffeffff call 0000095f 
> Local Halt Decider: Infinite Recursion Detected Simulation Stopped 
> Infinite recursion / Infinitely nested simulation criteria has been met 
> 
> (1) function X() is called twice in sequence from the same machine 
> address of Y() 
> ...[00000b2b][002115d2][00000b30](05) e82ffeffff call 0000095f 
> 
> (2) with the same parameters to X() 
> The pair of push instructions preceding call 0000095f push the value of 
> 0xb1f (The address of H_Hat) onto the stack as input to Halts(). 
> 
> (3) with no conditional branch or indexed jump instructions in Y() 
> No instructions between 0xb1f and 0xb2b of H_Hat() fit this category. 
> 
> (4) with no function call returns from X() 
> Halts() is a simulator that never returns to its input. 
> 
> ...[00000b62][0010153e][00000000](03) 83c408 add esp,+08 
> ...[00000b65][0010153e][00000000](03) 8945fc mov 
> [ebp-04],eax 
> ...[00000b68][0010153e][00000000](03) 8b45fc mov 
> eax,[ebp-04] 
> ...[00000b6b][0010153a][00000000](01) 50 push eax 
> ...[00000b6c][00101536][0000032b](05) 682b030000 push 0000032b 
> ...[00000b71][00101532][00000b76](05) e8e9f7ffff call 0000035f 
> Input_Would_Halt = 0 
> ...[00000b76][0010153e][00000000](03) 83c408 add esp,+08 
> ...[00000b79][0010153e][00000000](02) 33c0 xor eax,eax 
> ...[00000b7b][00101542][00000000](02) 8be5 mov esp,ebp 
> ...[00000b7d][00101546][00100000](01) 5d pop ebp 
> ...[00000b7e][0010154a][00000080](01) c3 ret 
> Number_of_User_Instructions(33) 
> Number of Instructions Executed(26560) 
> 
> I also updated this file with these clarifications: 
> http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf 
> 
> 
> 
> -- 
> Copyright 2021 Pete Olcott 
> 
> "Great spirits have always encountered violent opposition from mediocre 
> minds." Einstein

Please provide a valid C++ code and CONSISTENT, HONEST, descriptions.
Your statements are confusing,  not showing desire for Honest Dialogue

[toc] | [prev] | [next] | [standalone]


#79467 — Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not )

Fromolcott <NoOne@NoWhere.com>
Date2021-05-08 21:35 -0500
SubjectRe: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not )
Message-ID<D_qdnQo-tfTm1wr9nZ2dnUU7-SPNnZ2d@giganews.com>
In reply to#79466
On 5/8/2021 9:21 PM, wij wrote:
> On Sunday, 9 May 2021 at 06:45:48 UTC+8, olcott wrote:
>> On 5/8/2021 5:06 PM, Kaz Kylheku wrote:
>>> On 2021-05-08, olcott <No...@NoWhere.com> wrote:
>>>> On 5/8/2021 3:24 PM, Kaz Kylheku wrote:
>>>>> On 2021-05-08, olcott <No...@NoWhere.com> wrote:
>>>>>> Dishonest people are free to disagree with verified facts, honest people
>>>>>> are not.
>>>>>
>>>>> Yes; verified facts like uncomputability of halting, Gödel's
>>>>> incompleteness theorems and such.
>>>>>
>>>>
>>>> Removing this key context seems quite dishonest:
>>>>
>>>> On 5/8/2021 10:57 AM, Kaz Kylheku wrote:
>>>>> There is no evidence that H_Hat is forced to stop.
>>>>
>>>> I will not assume that dishonesty was your intention.
>>>>
>>>>>> The following execution trace proves that the input H_Hat()
>>>>>> <is> forced to stop at its machine address [00000b67].
>>>>>
>>>>> Your execution traces don't prove anything because they omit
>>>>> reams and reams of instructions.
>>>>
>>>> It does prove that H_Hat was forced to stop.
>>>
>>> Your own traces shows that H_Hat resumes. Here is one of them,
>>> abridged:
>>>
>>
>> In the following I show every single detail of exactly how the
>> non-halting behavior pattern of infinite recursion or infinitely nested
>> simulation has been matched by Halts((u32)H_Hat, (u32)H_Hat).
>>
>> The the only possible way that non-halting has been decided incorrectly
>> is an error in the criteria shown below.
>>
>>
>> When an execution trace matches the following criteria we know that the
>> non-halting behavior of infinite recursion or infinitely nested
>> simulation has been matched:
>>
>> If the execution trace of function Y() shows:
>> (1) function X() is called twice in sequence from the same machine
>> address of Y()
>> (2) with the same parameters to X()
>> (3) with no conditional branch or indexed jump instructions in Y()
>> (4) with no function call returns from X()
>> then the function call from Y() to X() is infinitely recursive.
>>
>> void H_Hat(u32 P)
>> {
>>   u32 Input_Halts = Halts(P, P);
>>   if (Input_Halts)
>>     HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
>> Output("Input_Would_Halt = ", Input_Would_Halt);
>> }
>>
>> _H_Hat()
>> [00000b1f](01) 55 push ebp
>> [00000b20](02) 8bec mov ebp,esp
>> [00000b22](01) 51 push ecx
>> [00000b23](03) 8b4508 mov eax,[ebp+08]
>> [00000b26](01) 50 push eax
>> [00000b27](03) 8b4d08 mov ecx,[ebp+08]
>> [00000b2a](01) 51 push ecx
>> [00000b2b](05) e82ffeffff call 0000095f
>> [00000b30](03) 83c408 add esp,+08
>> [00000b33](03) 8945fc mov [ebp-04],eax
>> [00000b36](04) 837dfc00 cmp dword [ebp-04],+00
>> [00000b3a](02) 7402 jz 00000b3e
>> [00000b3c](02) ebfe jmp 00000b3c
>> [00000b3e](02) 8be5 mov esp,ebp
>> [00000b40](01) 5d pop ebp
>> [00000b41](01) c3 ret
>> Size in bytes:(0035) [00000b41]
>>
>> _main()
>> [00000b4f](01) 55 push ebp
>> [00000b50](02) 8bec mov ebp,esp
>> [00000b52](01) 51 push ecx
>> [00000b53](05) 681f0b0000 push 00000b1f
>> [00000b58](05) 681f0b0000 push 00000b1f
>> [00000b5d](05) e8fdfdffff call 0000095f
>> [00000b62](03) 83c408 add esp,+08
>> [00000b65](03) 8945fc mov [ebp-04],eax
>> [00000b68](03) 8b45fc mov eax,[ebp-04]
>> [00000b6b](01) 50 push eax
>> [00000b6c](05) 682b030000 push 0000032b
>> [00000b71](05) e8e9f7ffff call 0000035f
>> [00000b76](03) 83c408 add esp,+08
>> [00000b79](02) 33c0 xor eax,eax
>> [00000b7b](02) 8be5 mov esp,ebp
>> [00000b7d](01) 5d pop ebp
>> [00000b7e](01) c3 ret
>> Size in bytes:(0048) [00000b7e]
>>
>> Columns
>> (1) Machine address of instruction
>> (2) Machine address of top of stack
>> (3) Value of top of stack after instruction executed
>> (4) Number of bytes of machine code
>> (5) Machine language bytes
>> (6) Assembly language text
>>
>> ...[00000b4f][00101542][00000000](01) 55 push ebp
>> ...[00000b50][00101542][00000000](02) 8bec mov ebp,esp
>> ...[00000b52][0010153e][00000000](01) 51 push ecx
>> ...[00000b53][0010153a][00000b1f](05) 681f0b0000 push 00000b1f
>> ...[00000b58][00101536][00000b1f](05) 681f0b0000 push 00000b1f
>> ...[00000b5d][00101532][00000b62](05) e8fdfdffff call 0000095f
>>
>> Begin Local Halt Decider Simulation at Machine Address:b1f
>> ...[00000b1f][002115e2][002115e6](01) 55 push ebp
>> ...[00000b20][002115e2][002115e6](02) 8bec mov ebp,esp
>> ...[00000b22][002115de][002015b2](01) 51 push ecx
>> ...[00000b23][002115de][002015b2](03) 8b4508 mov eax,[ebp+08]
>> ...[00000b26][002115da][00000b1f](01) 50 push eax
>> ...[00000b27][002115da][00000b1f](03) 8b4d08 mov ecx,[ebp+08]
>> ...[00000b2a][002115d6][00000b1f](01) 51 push ecx
>> ...[00000b2b][002115d2][00000b30](05) e82ffeffff call 0000095f
>> The above eight instructions repeat
>>
>> ...[00000b1f][0025c00a][0025c00e](01) 55 push ebp
>> ...[00000b20][0025c00a][0025c00e](02) 8bec mov ebp,esp
>> ...[00000b22][0025c006][0024bfda](01) 51 push ecx
>> ...[00000b23][0025c006][0024bfda](03) 8b4508 mov eax,[ebp+08]
>> ...[00000b26][0025c002][00000b1f](01) 50 push eax
>> ...[00000b27][0025c002][00000b1f](03) 8b4d08 mov ecx,[ebp+08]
>> ...[00000b2a][0025bffe][00000b1f](01) 51 push ecx
>> ...[00000b2b][0025bffa][00000b30](05) e82ffeffff call 0000095f
>> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
>> Infinite recursion / Infinitely nested simulation criteria has been met
>>
>> (1) function X() is called twice in sequence from the same machine
>> address of Y()
>> ...[00000b2b][002115d2][00000b30](05) e82ffeffff call 0000095f
>>
>> (2) with the same parameters to X()
>> The pair of push instructions preceding call 0000095f push the value of
>> 0xb1f (The address of H_Hat) onto the stack as input to Halts().
>>
>> (3) with no conditional branch or indexed jump instructions in Y()
>> No instructions between 0xb1f and 0xb2b of H_Hat() fit this category.
>>
>> (4) with no function call returns from X()
>> Halts() is a simulator that never returns to its input.
>>
>> ...[00000b62][0010153e][00000000](03) 83c408 add esp,+08
>> ...[00000b65][0010153e][00000000](03) 8945fc mov
>> [ebp-04],eax
>> ...[00000b68][0010153e][00000000](03) 8b45fc mov
>> eax,[ebp-04]
>> ...[00000b6b][0010153a][00000000](01) 50 push eax
>> ...[00000b6c][00101536][0000032b](05) 682b030000 push 0000032b
>> ...[00000b71][00101532][00000b76](05) e8e9f7ffff call 0000035f
>> Input_Would_Halt = 0
>> ...[00000b76][0010153e][00000000](03) 83c408 add esp,+08
>> ...[00000b79][0010153e][00000000](02) 33c0 xor eax,eax
>> ...[00000b7b][00101542][00000000](02) 8be5 mov esp,ebp
>> ...[00000b7d][00101546][00100000](01) 5d pop ebp
>> ...[00000b7e][0010154a][00000080](01) c3 ret
>> Number_of_User_Instructions(33)
>> Number of Instructions Executed(26560)
>>
>> I also updated this file with these clarifications:
>> http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf
>>
>>
>>
>> -- 
>> Copyright 2021 Pete Olcott
>>
>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein
> 
> Please provide a valid C++ code and CONSISTENT, HONEST, descriptions.
> Your statements are confusing,  not showing desire for Honest Dialogue
> 

The above paper has much more details.
This posting is the essence of my results.

u32 Halts(u32 P, u32 I);

The key C code is provided above. Halts() is actually quite complex 
depending on many hundreds of pages of x86 emulator code also written in 
C. The only thing that needs to be known about this otherwise enormously 
complex code is that Halts() simulates the code @ machine address P with 
data at machine address I until this simulation matches the non-halting 
criteria of (1)(2)(3)(4) shown above.

Putting all this together and the key halting problem instance is shown 
to be decidable as non-halting.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#79468 — Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not )

Fromwij <wyniijj@gmail.com>
Date2021-05-08 20:02 -0700
SubjectRe: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not )
Message-ID<18aac8e9-3640-4c1f-87f4-28e2a5bd8b70n@googlegroups.com>
In reply to#79467
> > ....
> > Please provide a valid C++ code and CONSISTENT, HONEST, descriptions. 
> > Your statements are confusing, not showing desire for Honest Dialogue 
> >
> The above paper has much more details. 
> This posting is the essence of my results. 
> 
> u32 Halts(u32 P, u32 I); 
> 
> The key C code is provided above. Halts() is actually quite complex 
> depending on many hundreds of pages of x86 emulator code also written in 
> C. The only thing that needs to be known about this otherwise enormously 
> complex code is that Halts() simulates the code @ machine address P with 
> data at machine address I until this simulation matches the non-halting 
> criteria of (1)(2)(3)(4) shown above. 
> 
> Putting all this together and the key halting problem instance is shown 
> to be decidable as non-halting.
> -- 
> Copyright 2021 Pete Olcott 
> 
> "Great spirits have always encountered violent opposition from mediocre 
> minds." Einstein

The non-halting criteria of (1)(2)(3)(4) mentions X(),Y(), while the examples
use u32 Halts(u32,u32), and H_Hat(u32). I am baffled what is really said.
(consistency)

[toc] | [prev] | [next] | [standalone]


#79469 — Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not )

Fromolcott <NoOne@NoWhere.com>
Date2021-05-08 22:11 -0500
SubjectRe: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not )
Message-ID<bJKdnfIDocxNzwr9nZ2dnUU7-Y-dnZ2d@giganews.com>
In reply to#79468
On 5/8/2021 10:02 PM, wij wrote:
>>> ....
>>> Please provide a valid C++ code and CONSISTENT, HONEST, descriptions.
>>> Your statements are confusing, not showing desire for Honest Dialogue
>>>
>> The above paper has much more details.
>> This posting is the essence of my results.
>>
>> u32 Halts(u32 P, u32 I);
>>
>> The key C code is provided above. Halts() is actually quite complex
>> depending on many hundreds of pages of x86 emulator code also written in
>> C. The only thing that needs to be known about this otherwise enormously
>> complex code is that Halts() simulates the code @ machine address P with
>> data at machine address I until this simulation matches the non-halting
>> criteria of (1)(2)(3)(4) shown above.
>>
>> Putting all this together and the key halting problem instance is shown
>> to be decidable as non-halting.
>> -- 
>> Copyright 2021 Pete Olcott
>>
>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein
> 
> The non-halting criteria of (1)(2)(3)(4) mentions X(),Y(), while the examples
> use u32 Halts(u32,u32), and H_Hat(u32). I am baffled what is really said.
> (consistency)
> 

The X() and Y() function names specify the generic [infinite-recursion] 
behavior pattern. This behavior pattern equally applies to the 
[infinitely nested simulation] behavior of H_Hat() relative to Halts().

I cut-and-pasted this stuff from my five page paper. The above is 
explained on page one of my paper.

http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c++


csiph-web