Path: ...!feeds.phibee-telecom.net!3.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Liar detector: Fred, Richard, Joes and Alan --- Ben's agreement
Date: Fri, 19 Jul 2024 11:51:33 +0300
Organization: -
Lines: 59
Message-ID: <v7d9el$2tp5s$1@dont-email.me>
References: <v644pn$29t4h$3@dont-email.me> <v6c539$3u2mj$1@dont-email.me> <v6dda0$7s8u$1@dont-email.me> <v6e67v$bbcb$4@dont-email.me> <v6gss2$t87a$1@dont-email.me> <v6gv65$to0m$1@dont-email.me> <v6h2li$ud7p$1@dont-email.me> <v6h2rm$ue7s$1@dont-email.me> <v6h3cu$ud7p$2@dont-email.me> <v6h83q$vag9$1@dont-email.me> <v6ikgb$19f5g$1@dont-email.me> <v6jgjo$1ctoi$4@dont-email.me> <v6lckp$1qi9e$1@dont-email.me> <v6m2qq$1tj30$6@dont-email.me> <60a1c2490e9bd9a5478fd173a20ed64d5eb158f9@i2pn2.org> <v6nvn8$2bn6q$1@dont-email.me> <v6oqti$2fuva$7@dont-email.me> <v6qn6k$2ubkt$1@dont-email.me> <v6r9q1$30qtt$5@dont-email.me> <v6tbge$3gegs$1@dont-email.me> <v6tqlm$3imib$5@dont-email.me> <v6vvid$24jd$1@dont-email.me> <v70mih$61d8$3@dont-email.me> <v72i9m$jne3$1@dont-email.me> <v7367p$mjis$8@dont-email.me> <v755m4$15kf6$1@dont-email.me> <v75vl9$19j7l$7@dont-email.me> <v77p77$1nm3r$1@dont-email.me> <v78fa7$1rc43$2@dont-email.me> <v7agsg$2am9u$1@dont-email.me> <v7b4l2$2e2aq$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 19 Jul 2024 10:51:33 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="f38904cb6ada6338ee5486d51c69675b";
	logging-data="3073212"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/teFH/GjyVghcve+msK7V+"
User-Agent: Unison/2.2
Cancel-Lock: sha1:PcAI6MvVzba7R8nb+gQP+lPlgUs=
Bytes: 4251

On 2024-07-18 13:17:22 +0000, olcott said:

> On 7/18/2024 2:40 AM, Mikko wrote:
>> On 2024-07-17 13:00:55 +0000, olcott said:
>> 
>>> On 7/17/2024 1:43 AM, Mikko wrote:
>>>> On 2024-07-16 14:21:28 +0000, olcott said:
>>>>> 
>>>>> When simulated input DDD stops running {if and only if}
>>>>> the simulation of this input DDD has been aborted this
>>>>> necessitates that input DDD specifies non-halting behavior
>>>> 
>>>> DDD does not stop runnig unless it is completely exeuted.
>>> 
>>> _DDD()
>>> [00002163] 55         push ebp      ; housekeeping
>>> [00002164] 8bec       mov ebp,esp   ; housekeeping
>>> [00002166] 6863210000 push 00002163 ; push DDD
>>> [0000216b] e853f4ffff call 000015c3 ; call HHH(DDD)
>>> [00002170] 83c404     add esp,+04
>>> [00002173] 5d         pop ebp
>>> [00002174] c3         ret
>>> Size in bytes:(0018) [00002174]
>>> 
>>> DDD emulated by HHH according to the semantic meaning of
>>> its x86 instructions never stop running unless aborted.
>> 
>> You mean HHH's simulation of DDD may not termite before HHH aborts it?
> 
> When we examine the infinite set of every HHH/DDD pair such that:
> HHH₁ one step of DDD₁ is correctly emulated by HHH₁.
> HHH₂ two steps of DDD₂ are correctly emulated by HHH₂.
> HHH₃ three steps of DDD₃ are correctly emulated by HHH₃.
> ...
> HHH∞ The emulation of DDD∞ by HHH∞ never stops running.
> 
> When each DDD of the HHH/DDD pairs above is correctly emulated
> by its corresponding HHH according to the semantic meaning of its
> x86 instructions it CANNOT POSSIBLY reach past its own machine
> address 0000216b, not even by an act of God.

You apparently mean that no HHHᵢ can simulate the corresponding DDDᵢ to
its termination? For every finite i the behaviour specified by  DDDᵢ is
halting.

>> The behaviour specified by DDD, both by C semantics and by x86 semantics,
>> is halting if HHH returns. Otherwise HHH is not a decider.
> 
> When HHH is required to be a pure function then only one element
> of the above infinite set of every possible HHH/DDD is not a decider.

The behavour of DDDᵢ depends on what HHHᵢ does. Wheter HHHᵢ is required
to what it does has no evvect on the behaviour of  DDDᵢ.

A pair is never a decider.

-- 
Mikko