Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Correcting the definition of the halting problem --- Computable functions
Date: Wed, 26 Mar 2025 09:08:46 +0200
Organization: -
Lines: 49
Message-ID: <vs095u$17t6d$1@dont-email.me>
References: <vr1shq$1qopn$1@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> <vrsogj$1q39o$3@dont-email.me> <vrsqlq$1rblu$4@dont-email.me> <vrsrmr$1q39o$4@dont-email.me> <vrt14i$264jb$1@dont-email.me> <vrt1tu$257a2$1@dont-email.me> <vrt357$264jb$2@dont-email.me> <vrt6va$22073$1@dont-email.me> <vrt7u2$2au0q$1@dont-email.me> <32b8ccf09a1f49fea01e5ae59f019b51c1db2c3c@i2pn2.org> <vrua83$38ob9$8@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 08:08:47 +0100 (CET)
Injection-Info: dont-email.me; posting-host="a41c375dff42617dc0105e6ad7e7bbd3";
	logging-data="1307853"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19NFE1b7ZQaSuPgBSBolAAz"
User-Agent: Unison/2.2
Cancel-Lock: sha1:U1O9Xcq1akT5bw/HCtn65eVwnTc=
Bytes: 4017

On 2025-03-25 13:14:43 +0000, olcott said:

> On 3/25/2025 3:32 AM, joes wrote:
>> Am Mon, 24 Mar 2025 22:29:06 -0500 schrieb olcott:
>>> On 3/24/2025 10:12 PM, dbush wrote:
>>>> On 3/24/2025 10:07 PM, olcott wrote:
>>>>> On 3/24/2025 8:46 PM, André G. Isaak wrote:
>>>>>> On 2025-03-24 19:33, olcott wrote:
>>>>>>> On 3/24/2025 7:00 PM, André G. Isaak wrote:
>>>>>> 
>>>>>>>> In the post you were responding to I pointed out that computable
>>>>>>>> functions are mathematical objects.
>>>>>>> Computable functions implemented using models of computation would
>>>>>>> seem to be more concrete than pure math functions.
>>>>>> Those are called computations or algorithms, not computable
>>>>>> functions.
>>>>> https://en.wikipedia.org/wiki/Pure_function Is another way to look at
>>>>> computable functions implemented by some concrete model of
>>>>> computation.
>>>> And not all mathematical functions are computable, such as the halting
>>>> function.
>> 
>>>>>> The halting problems asks whether there *is* an algorithm which can
>>>>>> compute the halting function, but the halting function itself is a
>>>>>> purely mathematical object which exists prior to, and independent of,
>>>>>> any such algorithm (if one existed).
>>>>> None-the-less it only has specific elements of its domain as its
>>>>> entire basis. For Turing machines this always means a finite string
>>>>> that (for example) encodes a specific sequence of moves.
>>>> False.  *All* turing machine are the domain of the halting function,
>>>> and the existence of UTMs show that all turning machines can be
>>>> described by a finite string.
>>> You just aren't paying enough attention. Turing machines are never in
>>> the domain of any computable function. <snip>
> 
>> Fine, their descriptions are, and their behaviour is computable -
>> by running them.
> 
> Halt deciders only report on the behavior that
> their input finite string specifies.

Quite obviously. A decider reports only one thing - otherwise it is not 
a decider. If that one thing is not whether the described computation 
halts
then it is not a halt decider.

-- 
Mikko