Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: "Fred. Zwarts" <F.Zwarts@HetNet.nl>
Newsgroups: comp.theory
Subject: Re: Correcting the definition of the halting problem --- Computable
 functions
Date: Wed, 26 Mar 2025 10:28:02 +0100
Organization: A noiseless patient Spider
Lines: 59
Message-ID: <vs0hb2$1ckla$8@dont-email.me>
References: <vr1shq$1qopn$1@dont-email.me> <vr9qu8$m4cu$2@dont-email.me>
 <vr9ttl$q57o$1@dont-email.me> <vr9u5m$q57o$2@dont-email.me>
 <vrbckn$23f4t$1@dont-email.me> <vrbtiq$2j07c$2@dont-email.me>
 <vrc3ud$2p461$1@dont-email.me> <vrc4nu$2m36k$5@dont-email.me>
 <vrkc2m$24ft6$1@dont-email.me> <vrkdij$25f9f$3@dont-email.me>
 <vrlt36$3haib$1@dont-email.me> <vrn237$im1e$1@dont-email.me>
 <vrn67b$md49$1@dont-email.me>
 <cb974817db8e02049daa5604d725300154e33ad1@i2pn2.org>
 <vrps14$35a4m$2@dont-email.me>
 <eab11e8806c669d296bff986870bdc6abdbb2fef@i2pn2.org>
 <vrqicu$3s258$1@dont-email.me>
 <30c2beae6c191f2502e93972a69c85ff227bfd03@i2pn2.org>
 <vrrs79$11a56$7@dont-email.me> <vrrsta$tdm5$1@dont-email.me>
 <vrs264$1a43i$1@dont-email.me> <vrs54q$1d1o2$1@dont-email.me>
 <vrse90$1jr8u$1@dont-email.me> <vrsk13$1q39o$1@dont-email.me>
 <vrsn62$1rblu$2@dont-email.me> <vrsnhu$1q39o$2@dont-email.me>
 <vrsodl$1rblu$3@dont-email.me>
 <e521a1335160c79dcc5d375738028f4deecda264@i2pn2.org>
 <vrvbmp$aq8m$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 26 Mar 2025 10:28:02 +0100 (CET)
Injection-Info: dont-email.me; posting-host="f6a5cf00636726f8011e12af665f7e80";
	logging-data="1462954"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/vflqQEuB/9WnSG430kLTi"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:Z+KpiEo3qh8s/R9aJYgeVIEm8HA=
In-Reply-To: <vrvbmp$aq8m$1@dont-email.me>
Content-Language: nl, en-GB

Op 25.mrt.2025 om 23:45 schreef olcott:
> On 3/25/2025 3:47 AM, joes wrote:
>> Am Mon, 24 Mar 2025 18:04:21 -0500 schrieb olcott:
>>> On 3/24/2025 5:49 PM, André G. Isaak wrote:
>>>> On 2025-03-24 16:43, olcott wrote:
>>>>
>>>>>> Computable functions don't have inputs. They have domains. Turing
>>>>>> machines have inputs.
>>>>> Maybe when pure math objects. In every model of computation they seem
>>>>> to always have inputs.
>>>> Computable functions *are* pure math objects. You seem to want to
>>>> conflate them with C functions, but that is not the case.
>>>> The crucial point is that the domains of computable functions are *not*
>>>> restricted to strings, even if the inputs to Turing Machines are.
>>>>
>>>>>> While the inputs to TMs are restricted to strings, there is no such
>>>>>> such restriction on computable functions.
>>>>>> The vast majority of computable functions of interest do *not* have
>>>>>> strings as their domains, yet they remain computable functions (a
>>>>>> simple example would be the parity function which maps NATURAL
>>>>>> NUMBERS (not strings) to yes/no values.)
>>>>> Since there is a bijection between natural numbers and strings of
>>>>> decimal digits your qualification seems vacuous.
>>>> There is not a bijection between natural numbers and strings. There is
>>>> a one-to-many mapping from natural numbers to strings, just as there is
>>>> a one-to-many mapping from computations (i.e. turing machine/input
>>>> string pairs, i.e. actual Turing machines directly running on their
>>>> inputs) to strings.
>>
>>> When III is emulated by pure emulator EEE for any finite number of steps
>>> of emulation according to the semantics of the x86 language it never
>>> reaches its own "ret" instruction final halt state THUS DOES NOT HALT.
>>> When III is directly executed calls an EEE instance that only emulates
>>> finite number of steps then this directly executed III always reaches
>>> its own "ret" instruction final halt state THUS HALTS.
> 
>> A pure simulator can not limit the number of steps. Also III doesn't
>> halt in, say, 3 steps. Why should III call a different instance
>> that doesn't abort, when it is being simulated?
>>
> 
> There is no different instance of EEE that doesn't abort.
> They all stop emulating after a finite number of steps.
> When EEE emulates 4 billion steps of III, III never
> reaches its final halt state.
> 

Indeed a simulator simulating itself will never reach the end of the 
simulation.
It is not very interesting to know whether a simulator reports that it 
is unable to reach the end of the simulation of a program that halts in 
direct execution.
It is interesting to know:
'Is there an algorithm that can determine for all possible inputs 
whether the input specifies a program that (according to the semantics 
of the machine language) halts when directly executed?'
This question seems undecidable for Olcott.