Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: Re: Correcting the definition of the halting problem --- Computable
 functions
Date: Tue, 25 Mar 2025 09:49:44 -0500
Organization: A noiseless patient Spider
Lines: 80
Message-ID: <vrufq8$3gia2$4@dont-email.me>
References: <vr1shq$1qopn$1@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> <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> <vrtska$30tvk$1@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 15:49:49 +0100 (CET)
Injection-Info: dont-email.me; posting-host="9741c665c88d9215381b06ce738934cb";
	logging-data="3688770"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18BEpRo4bw/iYCsvTHKZSY5"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:ODxNFD4rixw8NelaDKlEpCpxqzE=
Content-Language: en-US
X-Antivirus: Norton (VPS 250324-4, 3/24/2025), Outbound message
X-Antivirus-Status: Clean
In-Reply-To: <vrtska$30tvk$1@dont-email.me>
Bytes: 5116

On 3/25/2025 4:22 AM, Mikko wrote:
> On 2025-03-25 03:29:06 +0000, olcott said:
> 
>> 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>
> 
> There are computable functions that take Turing machines as arguments.
> For example, the number of states of a Turing machine.
> 
> The computability of a function requires that the domain can be mapped
> to finite strings.
> 

IT IS COUNTER-FACTUAL THAT A MACHINE DESCRIPTION SPECIFIES
BEHAVIOR IDENTICAL TO THE DIRECTLY EXECUTED MACHINE.

_III()
[00002172] 55         push ebp      ; housekeeping
[00002173] 8bec       mov  ebp,esp  ; housekeeping
[00002175] 6872210000 push 00002172 ; push III
[0000217a] e853f4ffff call 000015d2 ; call EEE(III)
[0000217f] 83c404     add  esp,+04
[00002182] 5d         pop  ebp
[00002183] c3         ret
Size in bytes:(0018) [00002183]

When any finite number of steps of III is emulated by
EEE according to the semantics of the x86 language the
emulated III never reaches its "ret" instruction final
halt state and the directly executed III does halt.

This conclusively proves that a machine description does
not always specify the same behavior as the directly
executed machine.

-- 
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer