Path: ...!Xl.tags.giganews.com!local-3.nntp.ord.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 28 Jul 2024 00:40:43 +0000
Subject: Re: This function proves that only the outermost HHH examines the
 execution trace
Newsgroups: comp.theory
References: <v80h07$2su8m$3@dont-email.me> <v82bi4$39v6n$4@dont-email.me>
 <v82tr5$3dftr$2@dont-email.me> <v82vtl$3dq41$2@dont-email.me>
 <v830hg$3dftr$9@dont-email.me> <v83des$2nhr$1@news.muc.de>
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Date: Sun, 28 Jul 2024 01:40:42 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.17
MIME-Version: 1.0
In-Reply-To: <v83des$2nhr$1@news.muc.de>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <KUidnalBUcYWDjj7nZ2dnZfqn_ednZ2d@brightview.co.uk>
Lines: 48
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-3WmFdvH5oVz0HlFSfcnsG9tSNh2ebEjaE6jVeOYbNHQHAvvyKHbtcnz78GozlgYlqyUUyvjh9eHS3SW!+QnebfOEUJ29UnCeFb5RYwE9gPIXwz+haeHGyzFplfKv+GyX248UkD1H/1iRoi77V92EiEwqlCFj!C0TCVpcIOevfSeqqk9dclXfLFJE=
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
Bytes: 4141

On 27/07/2024 19:14, Alan Mackenzie wrote:
> olcott <polcott333@gmail.com> wrote:
> 
>> Stopping running is not the same as halting.
>> DDD emulated by HHH stops running when its emulation has been aborted.
>> This is not the same as reaching its ret instruction and terminating
>> normally (AKA halting).
> 
> I think you're wrong, here.  All your C programs are a stand in for
> turing machines.  A turing machine is either running or halted.  There is
> no third state "aborted".  An aborted C program certainly doesn't
> correspond with a running turing machine - so it must be a halted turing
> machine.
> 
> So aborted programs are halted programs.  If you disagree, perhaps you
> could point out where in my arguments above I'm wrong.
> 

Aborting is an action performed by a simulator, not the TM being simulated.

If we want to count "aborted" as some kind of final status, it will have to be the status of a 
specific /PARTIAL SIMULATOR's/ simulation of a given computation.  That's not a property of the 
computation itself, as different partial simulators can simulate the same computation and terminate 
for different reasons.  Like HHH(DDD) aborts, while UTM(DDD) simulates to completion and so the 
final simulation status is halts.  [Neither of those outcomes contradict the fact that the 
computation DDD() halts.]

If some partial simulator halts when simulating a computation [as with UTM(DDD)] that implies the 
computation DDD() halts.  But if the simulator aborts, it doesn't say that much (in and of itself) 
about whether the /computation/ halts.  The halting problem statement is not concerned with 
simulations or how the simulations end.

Every time anyone in these PO threads says "halts" it ought to be 100% clear to everyone whether the 
computation itself is being discussed, or whether some simulation final status is intended.  (But 
that's far from being the case!)  Since the halting problem is concerned with computations halting 
and not how partial simulations are ended, I suggest that PO explicitly make clear that he is 
referring to simulations, whenever that is the case.  It seems reasonable that readers seeing 
"halts" with no further clarification can interpret that as actual computation behaviour, as that is 
how the term is always used in the literature.  Same with other terms like "reach"...

So when PO says "DDD simulated by HHH cannot reach its final ret instruction" is he talking about 
the computation DDD() [as defined mathematically], or its simulation by HHH?  He means the latter, 
but its far from clear, I'd say!  [I think most readers now have come around to reading it as a 
statement about simulations rather than the actual computation, which totally changes things...]


Mike.