Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: dbush <dbush.mobile@gmail.com>
Newsgroups: comp.theory
Subject: Re: Correcting the definition of the halting problem --- Computable
 functions
Date: Tue, 25 Mar 2025 11:02:58 -0400
Organization: A noiseless patient Spider
Lines: 61
Message-ID: <vrugj2$3hle3$3@dont-email.me>
References: <vr1shq$1qopn$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> <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> <vrufj5$3hle3$1@dont-email.me>
 <vrug1b$3gia2$5@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 25 Mar 2025 16:02:58 +0100 (CET)
Injection-Info: dont-email.me; posting-host="558cb3f1e92ebc1bf3f45b6c0d288267";
	logging-data="3724739"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+IuIgnWXi90c+yhMXodVBO"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:M7eL4DWXxXX9F9Vmalzwm3RPn+w=
In-Reply-To: <vrug1b$3gia2$5@dont-email.me>
Content-Language: en-US
Bytes: 4350

On 3/25/2025 10:53 AM, olcott wrote:
> On 3/25/2025 9:45 AM, dbush wrote:
>> On 3/24/2025 11:29 PM, olcott wrote:
>>> 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.
>>>>>>>
>>>>>>> https://en.wikipedia.org/wiki/Computable_function
>>>>>>>
>>>>>>> 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>
>>>
>>
>> False.  The mathematical function that counts the number of 
>> instructions in a turing machine is computable.
>>
> 
> It is impossible for an actual Turing machine to
> be input to any other TM.
> 

But a description of a turing machine can be, for example in the form of 
source code or a binary.  And a turing machine by definition *always* 
behaves the same for a given input when executing directly.