Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: Re: Simulation vs. Execution in the Halting Problem
Date: Fri, 30 May 2025 10:41:59 -0500
Organization: A noiseless patient Spider
Lines: 58
Message-ID: <101cjk7$hfof$7@dont-email.me>
References: <yU0_P.1529838$4AM6.776697@fx17.ams4>
 <101a7uv$3vfam$5@dont-email.me> <101br7m$db03$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 30 May 2025 17:42:00 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="73dc11aa65be162e0b0150944dd1d14a";
	logging-data="573199"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19U/VNpxsZU/xoee+QdYxMD"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:G+LMS6Bmm83wUc5SieD64BWSNAQ=
In-Reply-To: <101br7m$db03$1@dont-email.me>
X-Antivirus-Status: Clean
X-Antivirus: Norton (VPS 250530-4, 5/30/2025), Outbound message
Content-Language: en-US

On 5/30/2025 3:45 AM, Mikko wrote:
> On 2025-05-29 18:10:39 +0000, olcott said:
> 
>> On 5/29/2025 12:34 PM, Mr Flibble wrote:
>>>
>>> 🧠 Simulation vs. Execution in the Halting Problem
>>>
>>> In the classical framework of computation theory (Turing machines),
>>> simulation is not equivalent to execution, though they can 
>>> approximate one
>>> another.
>>
>> To the best of my knowledge a simulated input
>> always has the exact same behavior as the directly
>> executed input unless this simulated input calls
>> its own simulator.
> 
> The simulation of the behaviour should be equivalent to the real
> behaviour. 

That is the same as saying a function with infinite
recursion must have the same behavior as a function
without infinite recursion.

> Whether it actually is depends on the quality of the
> simulator. There is no exception for the case when the simulator
> is called. If the behaviour in the simulation is different from
> a real execution then the simulation is wrong.
> 

A function that calls its own simulator specifies different
behavior than a function that does not call its own simulator.

> One of the advantages of Turing machines is that there is no possibility
> to call anything so the effect of calling the simulator need not be
> considered.
> 

The same issue occurs in the Linz proof, it is merely more
difficult to see. The correctly simulated ⟨Ĥ⟩ ⟨Ĥ⟩ cannot
possibly reach its own simulated final halt state ⟨Ĥ.qn⟩

When Ĥ is applied to ⟨Ĥ⟩
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

(a) Ĥ copies its input ⟨Ĥ⟩
(b) Ĥ invokes embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩
(c) embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩
(d) simulated ⟨Ĥ⟩ copies its input ⟨Ĥ⟩
(e) simulated ⟨Ĥ⟩ invokes simulated embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩
(f) simulated embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩
(g) goto (d) with one more level of simulation


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