Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Simulation vs. Execution in the Halting Problem
Date: Tue, 10 Jun 2025 10:21:01 +0300
Organization: -
Lines: 114
Message-ID: <1028mct$13una$1@dont-email.me>
References: <yU0_P.1529838$4AM6.776697@fx17.ams4> <101a7uv$3vfam$5@dont-email.me> <101br7m$db03$1@dont-email.me> <101cjk7$hfof$7@dont-email.me> <101hdjt$21ui2$1@dont-email.me> <101iheg$2h3fr$1@dont-email.me> <1e5e5837ae9e60daa16e5fef3693ff424c1049d2@i2pn2.org> <101j60c$2urhr$3@dont-email.me> <101jiah$33qt3$1@dont-email.me> <101khgk$3bfvj$7@dont-email.me> <101m9fs$3sq20$1@dont-email.me> <101nlof$7qau$9@dont-email.me> <101osfh$mj67$1@dont-email.me> <101pqoc$ta6v$6@dont-email.me> <10237v8$3m1uq$1@dont-email.me> <10238o7$3m1s3$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 10 Jun 2025 09:21:01 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="348463ac74d67266c98b2e2c74f9d98c";
	logging-data="1178346"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+oV6ivi6O2qGi+dgm0TU2i"
User-Agent: Unison/2.2
Cancel-Lock: sha1:6RsV2/VvpkG5MP1QoMrw9tZAz/k=

On 2025-06-08 05:57:27 +0000, olcott said:

> On 6/8/2025 12:44 AM, Mikko wrote:
>> On 2025-06-04 16:03:24 +0000, olcott said:
>> 
>>> On 6/4/2025 2:26 AM, Mikko wrote:
>>>> On 2025-06-03 20:25:51 +0000, olcott said:
>>>> 
>>>>> On 6/3/2025 2:50 AM, Mikko wrote:
>>>>>> On 2025-06-02 15:55:00 +0000, olcott said:
>>>>>> 
>>>>>>> On 6/2/2025 2:02 AM, Mikko wrote:
>>>>>>>> On 2025-06-02 03:32:28 +0000, olcott said:
>>>>>>>> 
>>>>>>>>> On 6/1/2025 8:19 PM, Richard Damon wrote:
>>>>>>>>>> On 6/1/25 5:41 PM, olcott wrote:
>>>>>>>>>>> On 6/1/2025 6:30 AM, Mikko wrote:
>>>>>>>>>>>> On 2025-05-30 15:41:59 +0000, olcott said:
>>>>>>>>>>>> 
>>>>>>>>>>>>> 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.
>>>>>>>>>>>> 
>>>>>>>>>>>> A function does not have a behaviour. A function has a value for
>>>>>>>>>>>> every argument in its domain.
>>>>>>>>>>>> 
>>>>>>>>>>>> A function is not recursive. A definition of a function can be
>>>>>>>>>>>> recursive. There may be another way to define the same function
>>>>>>>>>>>> without recursion.
>>>>>>>>>>>> 
>>>>>>>>>>>> A definition of a function may use infinite recursion if it is also
>>>>>>>>>>>> defined how that infinite recursion defines a value.
>>>>>>>>>>>> 
>>>>>>>>>>>> Anyway, from the meaning of "simulation" follows that a simulation
>>>>>>>>>>>> of a behaviour is (at least in some sense) similar to the real
>>>>>>>>>>>> behaviour. Otherwise no simulation has happened.
>>>>>>>>>>>> 
>>>>>>>>>>> 
>>>>>>>>>>> void DDD()
>>>>>>>>>>> {
>>>>>>>>>>>    HHH(DDD);
>>>>>>>>>>>    return;
>>>>>>>>>>> }
>>>>>>>>>>> 
>>>>>>>>>>> The *input* to simulating termination analyzer HHH(DDD)
>>>>>>>>>>> specifies recursive simulation that can never reach its
>>>>>>>>>>> *simulated "return" instruction final halt state*
>>>>>>>>>>> 
>>>>>>>>>>> *Every rebuttal to this changes the words*
>>>>>>>>>>> 
>>>>>>>>>> 
>>>>>>>>>> No it doesn't, as HHH is defined to abort and simulation after finite 
>>>>>>>>>> time, and thus only does finite simulation.
>>>>>>>>>> 
>>>>>>>>> 
>>>>>>>>> See right there you changed the words.
>>>>>>>>> I said nothing about finite or infinite simulation.
>>>>>>>>> You said that I am wrong about something that I didn't even say.
>>>>>>>> 
>>>>>>>> Again you are trying a sraw man deception. RIchard Damon did not change
>>>>>>>> your words, he only wrote his own. He did not claim that you said anything
>>>>>>>> about "finite" or "infinite" but that you should understand the difference.
>>>>>>> 
>>>>>>> Unlike most people here I do understand that not
>>>>>>> possibly reaching a final halt state *is* non-halting behavior.
>>>>>> 
>>>>>> You don't understand it correctly. Whether a computation is halting is a
>>>>>> feature of the computation, not a particular exectuion of that coputation.
>>>>>> A halting computation is a halting computation even if its execution is
>>>>>> discontinued before reaching the final halt state.
>>>>> 
>>>>> int main()
>>>>> {
>>>>>    DDD(); // Do you understand that the HHH(DDD) that this DDD
>>>>> }        // calls is only accountable for the behavior of its
>>>>>           // input, and thus NOT accountable for the behavior
>>>>>           // of its caller?
>>>> 
>>>> I don't set any requirements on HHH. I just note that if HHH does not
>>>> return a value that means "halts" it is not a halt decider and not
>>>> even a partial halt decider, because the direct execution of DDD has
>>>> been shown to halt.
>>> 
>>> If HHH(DDD) is supposed to report on the behavior
>>> of the direct execution of DDD()
> 
> dbush insists that it is required.

In news:10241b0$3rjen$1@dont-email.me dbush says "It is both allowed and
possible" but that does not matter much. More important is that that
prohibition is not present in typcial textbooks or original articles.

-- 
Mikko