Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

"Never make any mistaeks." (Anonymous, in a mail discussion about to a kernel bug report.)


devel / comp.theory / simulation-based halt deciders

SubjectAuthor
* simulation-based halt decidersMr Flibble
+* simulation-based halt decidersolcott
|`* simulation-based halt decidersMr Flibble
| `* simulation-based halt decidersolcott
|  `* simulation-based halt decidersMr Flibble
|   `- simulation-based halt decidersolcott
`- simulation-based halt decidersRichard Damon

1
simulation-based halt deciders

<20220701163257.0000489b@reddwarf.jmc>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=35249&group=comp.theory#35249

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!rocksolid2!i2pn.org!aioe.org!news.uzoreto.com!npeer.as286.net!npeer-ng0.as286.net!peer03.ams1!peer.ams1.xlned.com!news.xlned.com!peer02.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx14.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory
Subject: simulation-based halt deciders
Message-ID: <20220701163257.0000489b@reddwarf.jmc>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Lines: 28
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Fri, 01 Jul 2022 15:32:50 UTC
Date: Fri, 1 Jul 2022 16:32:57 +0100
X-Received-Bytes: 1817
 by: Mr Flibble - Fri, 1 Jul 2022 15:32 UTC

Hi!

N.B. This post is not about the halting problem as I am NOT talking
about a program that includes [Strachey 1965] pathology designed to
defeat halting deciders.

Whilst a simulation-based halt decider can return a correct answer of
halting in finite time if its input halts isn't it the case that it is
effectively impossible for a simulation-based halt decider to return a
correct answer of non-halting as the simulation of a non-halting
input would never terminate as its input never halts?

To me this seems self evidently true so am I missing something?

Obviously certain classes of non-halting input can be correctly
simulated and decided on in finite time such as a trivial infinite loop
or a duplicate machine state but I suggest these comprise only a small
subset of possible non-halting inputs.

It is the case that a machine has a finite number of possible states
(as CPU registers, flags and RAM contents) however that number could
easily be larger than the number of atoms in the observable universe so
whilst any duplicate machine state can be detected in finite time this
time could easily exceed the age of the universe.

/Flibble

Re: simulation-based halt deciders

<2J6dnT63ZZATiCL_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=35252&group=comp.theory#35252

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!rocksolid2!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 01 Jul 2022 10:41:02 -0500
Date: Fri, 1 Jul 2022 10:41:01 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.11.0
Subject: Re: simulation-based halt deciders
Content-Language: en-US
Newsgroups: comp.theory
References: <20220701163257.0000489b@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220701163257.0000489b@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <2J6dnT63ZZATiCL_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 103
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-9uJvJcWVfgwsgXuszGJH04MJNsTOn4GlLg71BqOX6tRyPVLZl1bBL0eQgMhkeIPya7jRrw7vjrvzfFW!SlwLEYZ2K0pgn8GvAb/LEC31eJGPK6NHskfQo8TtN1D/rkKR6EyYAFXTLIJXjVlxb3AIQYpKBVmE
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 4816
X-Received-Bytes: 4938
 by: olcott - Fri, 1 Jul 2022 15:41 UTC

On 7/1/2022 10:32 AM, Mr Flibble wrote:
> Hi!
>
> N.B. This post is not about the halting problem as I am NOT talking
> about a program that includes [Strachey 1965] pathology designed to
> defeat halting deciders.
>
> Whilst a simulation-based halt decider can return a correct answer of
> halting in finite time if its input halts isn't it the case that it is
> effectively impossible for a simulation-based halt decider to return a
> correct answer of non-halting as the simulation of a non-halting
> input would never terminate as its input never halts?
>

void Infinite_Loop()
{ HERE: goto HERE;
}

int main()
{ Output("Input_Halts = ", H0((u32)Infinite_Loop));
}

_Infinite_Loop()
[00001102](01) 55 push ebp
[00001103](02) 8bec mov ebp,esp
[00001105](02) ebfe jmp 00001105
[00001107](01) 5d pop ebp
[00001108](01) c3 ret
Size in bytes:(0007) [00001108]

_main()
[00001192](01) 55 push ebp
[00001193](02) 8bec mov ebp,esp
[00001195](05) 6802110000 push 00001102
[0000119a](05) e8d3fbffff call 00000d72
[0000119f](03) 83c404 add esp,+04
[000011a2](01) 50 push eax
[000011a3](05) 68a3040000 push 000004a3
[000011a8](05) e845f3ffff call 000004f2
[000011ad](03) 83c408 add esp,+08
[000011b0](02) 33c0 xor eax,eax
[000011b2](01) 5d pop ebp
[000011b3](01) c3 ret
Size in bytes:(0034) [000011b3]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[00001192][00101ef8][00000000] 55 push ebp
[00001193][00101ef8][00000000] 8bec mov ebp,esp
[00001195][00101ef4][00001102] 6802110000 push 00001102
[0000119a][00101ef0][0000119f] e8d3fbffff call 00000d72

H0: Begin Simulation Execution Trace Stored at:211fac
Address_of_H0:d72
[00001102][00211f9c][00211fa0] 55 push ebp
[00001103][00211f9c][00211fa0] 8bec mov ebp,esp
[00001105][00211f9c][00211fa0] ebfe jmp 00001105
[00001105][00211f9c][00211fa0] ebfe jmp 00001105
H0: Infinite Loop Detected Simulation Stopped

[0000119f][00101ef8][00000000] 83c404 add esp,+04
[000011a2][00101ef4][00000000] 50 push eax
[000011a3][00101ef0][000004a3] 68a3040000 push 000004a3
[000011a8][00101ef0][000004a3] e845f3ffff call 000004f2
Input_Halts = 0
[000011ad][00101ef8][00000000] 83c408 add esp,+08
[000011b0][00101ef8][00000000] 33c0 xor eax,eax
[000011b2][00101efc][00100000] 5d pop ebp
[000011b3][00101f00][00000004] c3 ret
Number of Instructions Executed(554) == 8 Pages

> To me this seems self evidently true so am I missing something?
>

Yes you are missing sufficient technical skill to see that the above is
obviously correct.

> Obviously certain classes of non-halting input can be correctly
> simulated and decided on in finite time such as a trivial infinite loop
> or a duplicate machine state but I suggest these comprise only a small
> subset of possible non-halting inputs.
>
> It is the case that a machine has a finite number of possible states
> (as CPU registers, flags and RAM contents) however that number could
> easily be larger than the number of atoms in the observable universe so
> whilst any duplicate machine state can be detected in finite time this
> time could easily exceed the age of the universe.
>
> /Flibble
>
>

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Re: simulation-based halt deciders

<20220701164553.000077f9@reddwarf.jmc>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=35253&group=comp.theory#35253

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!usenet.goja.nl.eu.org!news.freedyn.de!newsreader4.netcologne.de!news.netcologne.de!peer01.ams1!peer.ams1.xlned.com!news.xlned.com!peer02.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx14.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory
Subject: Re: simulation-based halt deciders
Message-ID: <20220701164553.000077f9@reddwarf.jmc>
References: <20220701163257.0000489b@reddwarf.jmc>
<2J6dnT63ZZATiCL_nZ2dnUU7_8zNnZ2d@giganews.com>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Lines: 97
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Fri, 01 Jul 2022 15:45:46 UTC
Date: Fri, 1 Jul 2022 16:45:53 +0100
X-Received-Bytes: 4207
 by: Mr Flibble - Fri, 1 Jul 2022 15:45 UTC

On Fri, 1 Jul 2022 10:41:01 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 7/1/2022 10:32 AM, Mr Flibble wrote:
> > Hi!
> >
> > N.B. This post is not about the halting problem as I am NOT talking
> > about a program that includes [Strachey 1965] pathology designed to
> > defeat halting deciders.
> >
> > Whilst a simulation-based halt decider can return a correct answer
> > of halting in finite time if its input halts isn't it the case that
> > it is effectively impossible for a simulation-based halt decider to
> > return a correct answer of non-halting as the simulation of a
> > non-halting input would never terminate as its input never halts?
> >
>
> void Infinite_Loop()
> {
> HERE: goto HERE;
> }
>
> int main()
> {
> Output("Input_Halts = ", H0((u32)Infinite_Loop));
> }
>
> _Infinite_Loop()
> [00001102](01) 55 push ebp
> [00001103](02) 8bec mov ebp,esp
> [00001105](02) ebfe jmp 00001105
> [00001107](01) 5d pop ebp
> [00001108](01) c3 ret
> Size in bytes:(0007) [00001108]
>
> _main()
> [00001192](01) 55 push ebp
> [00001193](02) 8bec mov ebp,esp
> [00001195](05) 6802110000 push 00001102
> [0000119a](05) e8d3fbffff call 00000d72
> [0000119f](03) 83c404 add esp,+04
> [000011a2](01) 50 push eax
> [000011a3](05) 68a3040000 push 000004a3
> [000011a8](05) e845f3ffff call 000004f2
> [000011ad](03) 83c408 add esp,+08
> [000011b0](02) 33c0 xor eax,eax
> [000011b2](01) 5d pop ebp
> [000011b3](01) c3 ret
> Size in bytes:(0034) [000011b3]
>
> machine stack stack machine assembly
> address address data code language
> ======== ======== ======== ========= =============
> [00001192][00101ef8][00000000] 55 push ebp
> [00001193][00101ef8][00000000] 8bec mov ebp,esp
> [00001195][00101ef4][00001102] 6802110000 push 00001102
> [0000119a][00101ef0][0000119f] e8d3fbffff call 00000d72
>
> H0: Begin Simulation Execution Trace Stored at:211fac
> Address_of_H0:d72
> [00001102][00211f9c][00211fa0] 55 push ebp
> [00001103][00211f9c][00211fa0] 8bec mov ebp,esp
> [00001105][00211f9c][00211fa0] ebfe jmp 00001105
> [00001105][00211f9c][00211fa0] ebfe jmp 00001105
> H0: Infinite Loop Detected Simulation Stopped
>
> [0000119f][00101ef8][00000000] 83c404 add esp,+04
> [000011a2][00101ef4][00000000] 50 push eax
> [000011a3][00101ef0][000004a3] 68a3040000 push 000004a3
> [000011a8][00101ef0][000004a3] e845f3ffff call 000004f2
> Input_Halts = 0
> [000011ad][00101ef8][00000000] 83c408 add esp,+08
> [000011b0][00101ef8][00000000] 33c0 xor eax,eax
> [000011b2][00101efc][00100000] 5d pop ebp
> [000011b3][00101f00][00000004] c3 ret
> Number of Instructions Executed(554) == 8 Pages
>
>
> > To me this seems self evidently true so am I missing something?
> >
>
> Yes you are missing sufficient technical skill to see that the above
> is obviously correct.

You obviously didn't read my entire post:

> Obviously certain classes of non-halting input can be correctly
> simulated and decided on in finite time such as a trivial infinite
> loop

One reason why you are not credible and are getting nowhere is that you
refuse to fully read and understand what people write.

Feel free to apologise for the libel.

/Flibble

Re: simulation-based halt deciders

<f4ednWUUE8dOhCL_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=35254&group=comp.theory#35254

 copy link   Newsgroups: comp.theory sci.logic sci.math
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 01 Jul 2022 10:59:15 -0500
Date: Fri, 1 Jul 2022 10:59:13 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.11.0
Subject: Re: simulation-based halt deciders
Content-Language: en-US
Newsgroups: comp.theory,sci.logic,sci.math
References: <20220701163257.0000489b@reddwarf.jmc>
<2J6dnT63ZZATiCL_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220701164553.000077f9@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220701164553.000077f9@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <f4ednWUUE8dOhCL_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 173
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-hmHc/93dJMqqPpBZo5KoHhEKvuZdOWdyLSycsxa+JO92pUlQMVo7uFf63J1eNEyZ0Pe3tqCsRRCvywh!kVmrPDMF3O3+JVnlnyUa6pStC7Yy4YGBXFxfyzgevsf6ijeeJ+jCiSuhmfSghwVhChRp4zXjx0N8
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 7520
 by: olcott - Fri, 1 Jul 2022 15:59 UTC

On 7/1/2022 10:45 AM, Mr Flibble wrote:
> On Fri, 1 Jul 2022 10:41:01 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/1/2022 10:32 AM, Mr Flibble wrote:
>>> Hi!
>>>
>>> N.B. This post is not about the halting problem as I am NOT talking
>>> about a program that includes [Strachey 1965] pathology designed to
>>> defeat halting deciders.
>>>
>>> Whilst a simulation-based halt decider can return a correct answer
>>> of halting in finite time if its input halts isn't it the case that
>>> it is effectively impossible for a simulation-based halt decider to
>>> return a correct answer of non-halting as the simulation of a
>>> non-halting input would never terminate as its input never halts?
>>>
>>
>> void Infinite_Loop()
>> {
>> HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> Output("Input_Halts = ", H0((u32)Infinite_Loop));
>> }
>>
>> _Infinite_Loop()
>> [00001102](01) 55 push ebp
>> [00001103](02) 8bec mov ebp,esp
>> [00001105](02) ebfe jmp 00001105
>> [00001107](01) 5d pop ebp
>> [00001108](01) c3 ret
>> Size in bytes:(0007) [00001108]
>>
>> _main()
>> [00001192](01) 55 push ebp
>> [00001193](02) 8bec mov ebp,esp
>> [00001195](05) 6802110000 push 00001102
>> [0000119a](05) e8d3fbffff call 00000d72
>> [0000119f](03) 83c404 add esp,+04
>> [000011a2](01) 50 push eax
>> [000011a3](05) 68a3040000 push 000004a3
>> [000011a8](05) e845f3ffff call 000004f2
>> [000011ad](03) 83c408 add esp,+08
>> [000011b0](02) 33c0 xor eax,eax
>> [000011b2](01) 5d pop ebp
>> [000011b3](01) c3 ret
>> Size in bytes:(0034) [000011b3]
>>
>> machine stack stack machine assembly
>> address address data code language
>> ======== ======== ======== ========= =============
>> [00001192][00101ef8][00000000] 55 push ebp
>> [00001193][00101ef8][00000000] 8bec mov ebp,esp
>> [00001195][00101ef4][00001102] 6802110000 push 00001102
>> [0000119a][00101ef0][0000119f] e8d3fbffff call 00000d72
>>
>> H0: Begin Simulation Execution Trace Stored at:211fac
>> Address_of_H0:d72
>> [00001102][00211f9c][00211fa0] 55 push ebp
>> [00001103][00211f9c][00211fa0] 8bec mov ebp,esp
>> [00001105][00211f9c][00211fa0] ebfe jmp 00001105
>> [00001105][00211f9c][00211fa0] ebfe jmp 00001105
>> H0: Infinite Loop Detected Simulation Stopped
>>
>> [0000119f][00101ef8][00000000] 83c404 add esp,+04
>> [000011a2][00101ef4][00000000] 50 push eax
>> [000011a3][00101ef0][000004a3] 68a3040000 push 000004a3
>> [000011a8][00101ef0][000004a3] e845f3ffff call 000004f2
>> Input_Halts = 0
>> [000011ad][00101ef8][00000000] 83c408 add esp,+08
>> [000011b0][00101ef8][00000000] 33c0 xor eax,eax
>> [000011b2][00101efc][00100000] 5d pop ebp
>> [000011b3][00101f00][00000004] c3 ret
>> Number of Instructions Executed(554) == 8 Pages
>>
>>
>>> To me this seems self evidently true so am I missing something?
>>>
>>
>> Yes you are missing sufficient technical skill to see that the above
>> is obviously correct.
>
> You obviously didn't read my entire post:
>
>> Obviously certain classes of non-halting input can be correctly
>> simulated and decided on in finite time such as a trivial infinite
>> loop
>
> One reason why you are not credible and are getting nowhere is that you
> refuse to fully read and understand what people write.
>
> Feel free to apologise for the libel.
>
> /Flibble
>

So you finally admit that simulating halt decider can be correct on some
non-halting inputs? What about this one?

void Infinite_Recursion(int N)
{ Infinite_Recursion(N);
}

int main()
{ Output("Input_Halts = ", H((u32)Infinite_Loop, (u32)Infinite_Loop));
}

_Infinite_Recursion()
[000010f2](01) 55 push ebp
[000010f3](02) 8bec mov ebp,esp
[000010f5](03) 8b4508 mov eax,[ebp+08]
[000010f8](01) 50 push eax
[000010f9](05) e8f4ffffff call 000010f2
[000010fe](03) 83c404 add esp,+04
[00001101](01) 5d pop ebp
[00001102](01) c3 ret
Size in bytes:(0017) [00001102]

_main()
[000011b2](01) 55 push ebp
[000011b3](02) 8bec mov ebp,esp
[000011b5](05) 68e2100000 push 000010e2
[000011ba](05) 68e2100000 push 000010e2
[000011bf](05) e8aefdffff call 00000f72
[000011c4](03) 83c408 add esp,+08
[000011c7](01) 50 push eax
[000011c8](05) 68a3040000 push 000004a3
[000011cd](05) e820f3ffff call 000004f2
[000011d2](03) 83c408 add esp,+08
[000011d5](02) 33c0 xor eax,eax
[000011d7](01) 5d pop ebp
[000011d8](01) c3 ret
Size in bytes:(0039) [000011d8]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[000011b2][00101f43][00000000] 55 push ebp
[000011b3][00101f43][00000000] 8bec mov ebp,esp
[000011b5][00101f3f][000010e2] 68e2100000 push 000010e2
[000011ba][00101f3b][000010e2] 68e2100000 push 000010e2
[000011bf][00101f37][000011c4] e8aefdffff call 00000f72

H: Begin Simulation Execution Trace Stored at:211ff7
Address_of_H:f72
[000010e2][00211fe3][00211fe7] 55 push ebp
[000010e3][00211fe3][00211fe7] 8bec mov ebp,esp
[000010e5][00211fe3][00211fe7] ebfe jmp 000010e5
[000010e5][00211fe3][00211fe7] ebfe jmp 000010e5
H: Infinite Loop Detected Simulation Stopped

[000011c4][00101f43][00000000] 83c408 add esp,+08
[000011c7][00101f3f][00000000] 50 push eax
[000011c8][00101f3b][000004a3] 68a3040000 push 000004a3
[000011cd][00101f3b][000004a3] e820f3ffff call 000004f2
Input_Halts = 0
[000011d2][00101f43][00000000] 83c408 add esp,+08
[000011d5][00101f43][00000000] 33c0 xor eax,eax
[000011d7][00101f47][00100000] 5d pop ebp
[000011d8][00101f4b][00000000] c3 ret
Number of Instructions Executed(573) == 9 Pages

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Re: simulation-based halt deciders

<20220701170957.00003a4b@reddwarf.jmc>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=35255&group=comp.theory#35255

 copy link   Newsgroups: comp.theory sci.logic sci.math
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!peer01.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx14.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory,sci.logic,sci.math
Subject: Re: simulation-based halt deciders
Message-ID: <20220701170957.00003a4b@reddwarf.jmc>
References: <20220701163257.0000489b@reddwarf.jmc>
<2J6dnT63ZZATiCL_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220701164553.000077f9@reddwarf.jmc>
<f4ednWUUE8dOhCL_nZ2dnUU7_8zNnZ2d@giganews.com>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Lines: 185
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Fri, 01 Jul 2022 16:09:50 UTC
Date: Fri, 1 Jul 2022 17:09:57 +0100
X-Received-Bytes: 8093
 by: Mr Flibble - Fri, 1 Jul 2022 16:09 UTC

On Fri, 1 Jul 2022 10:59:13 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 7/1/2022 10:45 AM, Mr Flibble wrote:
> > On Fri, 1 Jul 2022 10:41:01 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> On 7/1/2022 10:32 AM, Mr Flibble wrote:
> >>> Hi!
> >>>
> >>> N.B. This post is not about the halting problem as I am NOT
> >>> talking about a program that includes [Strachey 1965] pathology
> >>> designed to defeat halting deciders.
> >>>
> >>> Whilst a simulation-based halt decider can return a correct answer
> >>> of halting in finite time if its input halts isn't it the case
> >>> that it is effectively impossible for a simulation-based halt
> >>> decider to return a correct answer of non-halting as the
> >>> simulation of a non-halting input would never terminate as its
> >>> input never halts?
> >>
> >> void Infinite_Loop()
> >> {
> >> HERE: goto HERE;
> >> }
> >>
> >> int main()
> >> {
> >> Output("Input_Halts = ", H0((u32)Infinite_Loop));
> >> }
> >>
> >> _Infinite_Loop()
> >> [00001102](01) 55 push ebp
> >> [00001103](02) 8bec mov ebp,esp
> >> [00001105](02) ebfe jmp 00001105
> >> [00001107](01) 5d pop ebp
> >> [00001108](01) c3 ret
> >> Size in bytes:(0007) [00001108]
> >>
> >> _main()
> >> [00001192](01) 55 push ebp
> >> [00001193](02) 8bec mov ebp,esp
> >> [00001195](05) 6802110000 push 00001102
> >> [0000119a](05) e8d3fbffff call 00000d72
> >> [0000119f](03) 83c404 add esp,+04
> >> [000011a2](01) 50 push eax
> >> [000011a3](05) 68a3040000 push 000004a3
> >> [000011a8](05) e845f3ffff call 000004f2
> >> [000011ad](03) 83c408 add esp,+08
> >> [000011b0](02) 33c0 xor eax,eax
> >> [000011b2](01) 5d pop ebp
> >> [000011b3](01) c3 ret
> >> Size in bytes:(0034) [000011b3]
> >>
> >> machine stack stack machine assembly
> >> address address data code language
> >> ======== ======== ======== ========= =============
> >> [00001192][00101ef8][00000000] 55 push ebp
> >> [00001193][00101ef8][00000000] 8bec mov ebp,esp
> >> [00001195][00101ef4][00001102] 6802110000 push 00001102
> >> [0000119a][00101ef0][0000119f] e8d3fbffff call 00000d72
> >>
> >> H0: Begin Simulation Execution Trace Stored at:211fac
> >> Address_of_H0:d72
> >> [00001102][00211f9c][00211fa0] 55 push ebp
> >> [00001103][00211f9c][00211fa0] 8bec mov ebp,esp
> >> [00001105][00211f9c][00211fa0] ebfe jmp 00001105
> >> [00001105][00211f9c][00211fa0] ebfe jmp 00001105
> >> H0: Infinite Loop Detected Simulation Stopped
> >>
> >> [0000119f][00101ef8][00000000] 83c404 add esp,+04
> >> [000011a2][00101ef4][00000000] 50 push eax
> >> [000011a3][00101ef0][000004a3] 68a3040000 push 000004a3
> >> [000011a8][00101ef0][000004a3] e845f3ffff call 000004f2
> >> Input_Halts = 0
> >> [000011ad][00101ef8][00000000] 83c408 add esp,+08
> >> [000011b0][00101ef8][00000000] 33c0 xor eax,eax
> >> [000011b2][00101efc][00100000] 5d pop ebp
> >> [000011b3][00101f00][00000004] c3 ret
> >> Number of Instructions Executed(554) == 8 Pages
> >>
> >>
> >>> To me this seems self evidently true so am I missing something?
> >>>
> >>
> >> Yes you are missing sufficient technical skill to see that the
> >> above is obviously correct.
> >
> > You obviously didn't read my entire post:
> >
> >> Obviously certain classes of non-halting input can be correctly
> >> simulated and decided on in finite time such as a trivial infinite
> >> loop
> >
> > One reason why you are not credible and are getting nowhere is that
> > you refuse to fully read and understand what people write.
> >
> > Feel free to apologise for the libel.
> >
> > /Flibble
> >
>
> So you finally admit that simulating halt decider can be correct on
> some non-halting inputs? What about this one?
>
> void Infinite_Recursion(int N)
> {
> Infinite_Recursion(N);
> }
>
> int main()
> {
> Output("Input_Halts = ", H((u32)Infinite_Loop,
> (u32)Infinite_Loop)); }
>
> _Infinite_Recursion()
> [000010f2](01) 55 push ebp
> [000010f3](02) 8bec mov ebp,esp
> [000010f5](03) 8b4508 mov eax,[ebp+08]
> [000010f8](01) 50 push eax
> [000010f9](05) e8f4ffffff call 000010f2
> [000010fe](03) 83c404 add esp,+04
> [00001101](01) 5d pop ebp
> [00001102](01) c3 ret
> Size in bytes:(0017) [00001102]
>
> _main()
> [000011b2](01) 55 push ebp
> [000011b3](02) 8bec mov ebp,esp
> [000011b5](05) 68e2100000 push 000010e2
> [000011ba](05) 68e2100000 push 000010e2
> [000011bf](05) e8aefdffff call 00000f72
> [000011c4](03) 83c408 add esp,+08
> [000011c7](01) 50 push eax
> [000011c8](05) 68a3040000 push 000004a3
> [000011cd](05) e820f3ffff call 000004f2
> [000011d2](03) 83c408 add esp,+08
> [000011d5](02) 33c0 xor eax,eax
> [000011d7](01) 5d pop ebp
> [000011d8](01) c3 ret
> Size in bytes:(0039) [000011d8]
>
> machine stack stack machine assembly
> address address data code language
> ======== ======== ======== ========= =============
> [000011b2][00101f43][00000000] 55 push ebp
> [000011b3][00101f43][00000000] 8bec mov ebp,esp
> [000011b5][00101f3f][000010e2] 68e2100000 push 000010e2
> [000011ba][00101f3b][000010e2] 68e2100000 push 000010e2
> [000011bf][00101f37][000011c4] e8aefdffff call 00000f72
>
> H: Begin Simulation Execution Trace Stored at:211ff7
> Address_of_H:f72
> [000010e2][00211fe3][00211fe7] 55 push ebp
> [000010e3][00211fe3][00211fe7] 8bec mov ebp,esp
> [000010e5][00211fe3][00211fe7] ebfe jmp 000010e5
> [000010e5][00211fe3][00211fe7] ebfe jmp 000010e5
> H: Infinite Loop Detected Simulation Stopped
>
> [000011c4][00101f43][00000000] 83c408 add esp,+08
> [000011c7][00101f3f][00000000] 50 push eax
> [000011c8][00101f3b][000004a3] 68a3040000 push 000004a3
> [000011cd][00101f3b][000004a3] e820f3ffff call 000004f2
> Input_Halts = 0
> [000011d2][00101f43][00000000] 83c408 add esp,+08
> [000011d5][00101f43][00000000] 33c0 xor eax,eax
> [000011d7][00101f47][00100000] 5d pop ebp
> [000011d8][00101f4b][00000000] c3 ret
> Number of Instructions Executed(573) == 9 Pages
I have never denied that a simulation-based halting decider can decide
SOME non-halting inputs, what I have claimed is that a simulation-based
halting decider cannot decide, in realistic finite time, ALL
non-halting inputs as it is the wrong approach for the general case.

This post had nothing to do with your approach of trying to refute
[Strachey 1965]-based proofs as I stated at the top of my original
post. As far as that is concerned your approach is erroneous as you
always assume that if an input calls the decider then it is
automatically pathological. You also refuse to accept that [Strachey
1965] does NOT involve any infinite recursion which is purely a
manifestation of your erroneous approach.

/Flibble

Re: simulation-based halt deciders

<DqmdnQcyuKvpuiL_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=35259&group=comp.theory#35259

 copy link   Newsgroups: comp.theory sci.logic sci.math
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!feeder.usenetexpress.com!tr3.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 01 Jul 2022 11:57:24 -0500
Date: Fri, 1 Jul 2022 11:57:23 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0
Subject: Re: simulation-based halt deciders
Content-Language: en-US
Newsgroups: comp.theory,sci.logic,sci.math
References: <20220701163257.0000489b@reddwarf.jmc> <2J6dnT63ZZATiCL_nZ2dnUU7_8zNnZ2d@giganews.com> <20220701164553.000077f9@reddwarf.jmc> <f4ednWUUE8dOhCL_nZ2dnUU7_8zNnZ2d@giganews.com> <20220701170957.00003a4b@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220701170957.00003a4b@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <DqmdnQcyuKvpuiL_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 279
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-qbc1kWOHZFCMpw/kuu513vWQdReT/rJEm8S/KpKlVxzXFv++L25Z3rksHwOyXfG6EEWjI/LD2/PB+/C!2fJn7VLNVZGqvz5J9Hug77ilbZ3I2fDjiFAFHfc3NTe5gnjIUNaubpDhx28ZQ+Ej8vPUzmEQ/+hM
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 12206
X-Received-Bytes: 12341
 by: olcott - Fri, 1 Jul 2022 16:57 UTC

On 7/1/2022 11:09 AM, Mr Flibble wrote:
> On Fri, 1 Jul 2022 10:59:13 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/1/2022 10:45 AM, Mr Flibble wrote:
>>> On Fri, 1 Jul 2022 10:41:01 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 7/1/2022 10:32 AM, Mr Flibble wrote:
>>>>> Hi!
>>>>>
>>>>> N.B. This post is not about the halting problem as I am NOT
>>>>> talking about a program that includes [Strachey 1965] pathology
>>>>> designed to defeat halting deciders.
>>>>>
>>>>> Whilst a simulation-based halt decider can return a correct answer
>>>>> of halting in finite time if its input halts isn't it the case
>>>>> that it is effectively impossible for a simulation-based halt
>>>>> decider to return a correct answer of non-halting as the
>>>>> simulation of a non-halting input would never terminate as its
>>>>> input never halts?
>>>>
>>>> void Infinite_Loop()
>>>> {
>>>> HERE: goto HERE;
>>>> }
>>>>
>>>> int main()
>>>> {
>>>> Output("Input_Halts = ", H0((u32)Infinite_Loop));
>>>> }
>>>>
>>>> _Infinite_Loop()
>>>> [00001102](01) 55 push ebp
>>>> [00001103](02) 8bec mov ebp,esp
>>>> [00001105](02) ebfe jmp 00001105
>>>> [00001107](01) 5d pop ebp
>>>> [00001108](01) c3 ret
>>>> Size in bytes:(0007) [00001108]
>>>>
>>>> _main()
>>>> [00001192](01) 55 push ebp
>>>> [00001193](02) 8bec mov ebp,esp
>>>> [00001195](05) 6802110000 push 00001102
>>>> [0000119a](05) e8d3fbffff call 00000d72
>>>> [0000119f](03) 83c404 add esp,+04
>>>> [000011a2](01) 50 push eax
>>>> [000011a3](05) 68a3040000 push 000004a3
>>>> [000011a8](05) e845f3ffff call 000004f2
>>>> [000011ad](03) 83c408 add esp,+08
>>>> [000011b0](02) 33c0 xor eax,eax
>>>> [000011b2](01) 5d pop ebp
>>>> [000011b3](01) c3 ret
>>>> Size in bytes:(0034) [000011b3]
>>>>
>>>> machine stack stack machine assembly
>>>> address address data code language
>>>> ======== ======== ======== ========= =============
>>>> [00001192][00101ef8][00000000] 55 push ebp
>>>> [00001193][00101ef8][00000000] 8bec mov ebp,esp
>>>> [00001195][00101ef4][00001102] 6802110000 push 00001102
>>>> [0000119a][00101ef0][0000119f] e8d3fbffff call 00000d72
>>>>
>>>> H0: Begin Simulation Execution Trace Stored at:211fac
>>>> Address_of_H0:d72
>>>> [00001102][00211f9c][00211fa0] 55 push ebp
>>>> [00001103][00211f9c][00211fa0] 8bec mov ebp,esp
>>>> [00001105][00211f9c][00211fa0] ebfe jmp 00001105
>>>> [00001105][00211f9c][00211fa0] ebfe jmp 00001105
>>>> H0: Infinite Loop Detected Simulation Stopped
>>>>
>>>> [0000119f][00101ef8][00000000] 83c404 add esp,+04
>>>> [000011a2][00101ef4][00000000] 50 push eax
>>>> [000011a3][00101ef0][000004a3] 68a3040000 push 000004a3
>>>> [000011a8][00101ef0][000004a3] e845f3ffff call 000004f2
>>>> Input_Halts = 0
>>>> [000011ad][00101ef8][00000000] 83c408 add esp,+08
>>>> [000011b0][00101ef8][00000000] 33c0 xor eax,eax
>>>> [000011b2][00101efc][00100000] 5d pop ebp
>>>> [000011b3][00101f00][00000004] c3 ret
>>>> Number of Instructions Executed(554) == 8 Pages
>>>>
>>>>
>>>>> To me this seems self evidently true so am I missing something?
>>>>>
>>>>
>>>> Yes you are missing sufficient technical skill to see that the
>>>> above is obviously correct.
>>>
>>> You obviously didn't read my entire post:
>>>
>>>> Obviously certain classes of non-halting input can be correctly
>>>> simulated and decided on in finite time such as a trivial infinite
>>>> loop
>>>
>>> One reason why you are not credible and are getting nowhere is that
>>> you refuse to fully read and understand what people write.
>>>
>>> Feel free to apologise for the libel.
>>>
>>> /Flibble
>>>
>>
>> So you finally admit that simulating halt decider can be correct on
>> some non-halting inputs? What about this one?
>>
>> void Infinite_Recursion(int N)
>> {
>> Infinite_Recursion(N);
>> }
>>
>> int main()
>> {
>> Output("Input_Halts = ", H((u32)Infinite_Loop,
>> (u32)Infinite_Loop)); }
>>
>> _Infinite_Recursion()
>> [000010f2](01) 55 push ebp
>> [000010f3](02) 8bec mov ebp,esp
>> [000010f5](03) 8b4508 mov eax,[ebp+08]
>> [000010f8](01) 50 push eax
>> [000010f9](05) e8f4ffffff call 000010f2
>> [000010fe](03) 83c404 add esp,+04
>> [00001101](01) 5d pop ebp
>> [00001102](01) c3 ret
>> Size in bytes:(0017) [00001102]
>>
>> _main()
>> [000011b2](01) 55 push ebp
>> [000011b3](02) 8bec mov ebp,esp
>> [000011b5](05) 68e2100000 push 000010e2
>> [000011ba](05) 68e2100000 push 000010e2
>> [000011bf](05) e8aefdffff call 00000f72
>> [000011c4](03) 83c408 add esp,+08
>> [000011c7](01) 50 push eax
>> [000011c8](05) 68a3040000 push 000004a3
>> [000011cd](05) e820f3ffff call 000004f2
>> [000011d2](03) 83c408 add esp,+08
>> [000011d5](02) 33c0 xor eax,eax
>> [000011d7](01) 5d pop ebp
>> [000011d8](01) c3 ret
>> Size in bytes:(0039) [000011d8]
>>
>> machine stack stack machine assembly
>> address address data code language
>> ======== ======== ======== ========= =============
>> [000011b2][00101f43][00000000] 55 push ebp
>> [000011b3][00101f43][00000000] 8bec mov ebp,esp
>> [000011b5][00101f3f][000010e2] 68e2100000 push 000010e2
>> [000011ba][00101f3b][000010e2] 68e2100000 push 000010e2
>> [000011bf][00101f37][000011c4] e8aefdffff call 00000f72
>>
>> H: Begin Simulation Execution Trace Stored at:211ff7
>> Address_of_H:f72
>> [000010e2][00211fe3][00211fe7] 55 push ebp
>> [000010e3][00211fe3][00211fe7] 8bec mov ebp,esp
>> [000010e5][00211fe3][00211fe7] ebfe jmp 000010e5
>> [000010e5][00211fe3][00211fe7] ebfe jmp 000010e5
>> H: Infinite Loop Detected Simulation Stopped
>>
>> [000011c4][00101f43][00000000] 83c408 add esp,+08
>> [000011c7][00101f3f][00000000] 50 push eax
>> [000011c8][00101f3b][000004a3] 68a3040000 push 000004a3
>> [000011cd][00101f3b][000004a3] e820f3ffff call 000004f2
>> Input_Halts = 0
>> [000011d2][00101f43][00000000] 83c408 add esp,+08
>> [000011d5][00101f43][00000000] 33c0 xor eax,eax
>> [000011d7][00101f47][00100000] 5d pop ebp
>> [000011d8][00101f4b][00000000] c3 ret
>> Number of Instructions Executed(573) == 9 Pages
>
> I have never denied that a simulation-based halting decider can decide
> SOME non-halting inputs, what I have claimed is that a simulation-based
> halting decider cannot decide, in realistic finite time, ALL
> non-halting inputs as it is the wrong approach for the general case.
>
> This post had nothing to do with your approach of trying to refute
> [Strachey 1965]-based proofs as I stated at the top of my original
> post. As far as that is concerned your approach is erroneous as you
> always assume that if an input calls the decider then it is
> automatically pathological.

// rec routine P
// §L :if T[P] go to L
// Return §
// https://academic.oup.com/comjnl/article/7/4/313/354243
void Strachey_P()
{ L:if (T(Strachey_P))
goto L;
return;
}

int main()
{ Output("Input_Halts = ", T(Strachey_P));
}

_Strachey_P()
[000015b2](01) 55 push ebp
[000015b3](02) 8bec mov ebp,esp
[000015b5](05) 68b2150000 push 000015b2 // push Strachey_P
[000015ba](05) e813fdffff call 000012d2 // call T
[000015bf](03) 83c404 add esp,+04
[000015c2](02) 85c0 test eax,eax
[000015c4](02) 7402 jz 000015c8
[000015c6](02) ebed jmp 000015b5
[000015c8](01) 5d pop ebp
[000015c9](01) c3 ret
Size in bytes:(0024) [000015c9]


Click here to read the complete article
Re: simulation-based halt deciders

<yYJvK.417732$zgr9.342226@fx13.iad>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=35269&group=comp.theory#35269

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!news-out.netnews.com!news.alt.net!fdc2.netnews.com!peer03.ams1!peer.ams1.xlned.com!news.xlned.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx13.iad.POSTED!not-for-mail
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0)
Gecko/20100101 Thunderbird/91.11.0
Subject: Re: simulation-based halt deciders
Content-Language: en-US
Newsgroups: comp.theory
References: <20220701163257.0000489b@reddwarf.jmc>
From: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <20220701163257.0000489b@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Lines: 51
Message-ID: <yYJvK.417732$zgr9.342226@fx13.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Fri, 1 Jul 2022 17:48:13 -0400
X-Received-Bytes: 3273
 by: Richard Damon - Fri, 1 Jul 2022 21:48 UTC

On 7/1/22 11:32 AM, Mr Flibble wrote:
> Hi!
>
> N.B. This post is not about the halting problem as I am NOT talking
> about a program that includes [Strachey 1965] pathology designed to
> defeat halting deciders.
>
> Whilst a simulation-based halt decider can return a correct answer of
> halting in finite time if its input halts isn't it the case that it is
> effectively impossible for a simulation-based halt decider to return a
> correct answer of non-halting as the simulation of a non-halting
> input would never terminate as its input never halts?
>
> To me this seems self evidently true so am I missing something?
>
> Obviously certain classes of non-halting input can be correctly
> simulated and decided on in finite time such as a trivial infinite loop
> or a duplicate machine state but I suggest these comprise only a small
> subset of possible non-halting inputs.
>
> It is the case that a machine has a finite number of possible states
> (as CPU registers, flags and RAM contents) however that number could
> easily be larger than the number of atoms in the observable universe so
> whilst any duplicate machine state can be detected in finite time this
> time could easily exceed the age of the universe.
>
> /Flibble
>
>

There are two distinct classes of non-halting programs:

1) Those that limit their state to a finite size, and
2) Those that grow their state space without limit.

A simulating Halt Decider can theoretically detect a repeat in the state
for the first case, but might not for the second. A simple way to detect
the duplicate state without needing exponential storage is to run two
copies of the input, one stepping two steps for a single step of the
other. A finite sized non-halting machine will my necessity get into a
fixed loop, and at some point the slower machine will end up exactly N
loops behind the faster machine and have a repeated state.

This method does NOT work for a non-halting machine that continues to
grow in 'size' over time. There can be other algorithms that might
handle some of them, and the question becomes can you show that you can
find a way that handles them all.

The "impossible program" shows that you can't. Peter's "proof" is based
on assuming you can, but never tries to prove it, so is just falling
into a fallacy.

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor