Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!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 ---HHH(DD)
Date: Tue, 25 Mar 2025 12:18:07 -0500
Organization: A noiseless patient Spider
Lines: 125
Message-ID: <vruogg$3n7k6$3@dont-email.me>
References: <vr1shq$1qopn$1@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> <vrugj2$3hle3$3@dont-email.me>
 <vruh6d$3j3me$2@dont-email.me> <vruhf1$3hle3$4@dont-email.me>
 <vrumaj$3n7k6$1@dont-email.me> <vrumke$3hle3$5@dont-email.me>
 <vrun8e$3n7k6$2@dont-email.me> <vrunm9$3hle3$6@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 18:18:10 +0100 (CET)
Injection-Info: dont-email.me; posting-host="28b8eab6d237e557af892b2ab104f6c1";
	logging-data="3907206"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19MtsRSFXtGpmvZQNvypUNk"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:WNU5B5Z5Obg8r7duN3UQIljbWss=
X-Antivirus: Norton (VPS 250325-18, 3/25/2025), Outbound message
In-Reply-To: <vrunm9$3hle3$6@dont-email.me>
X-Antivirus-Status: Clean
Content-Language: en-US
Bytes: 7027

On 3/25/2025 12:04 PM, dbush wrote:
> On 3/25/2025 12:56 PM, olcott wrote:
>> On 3/25/2025 11:46 AM, dbush wrote:
>>> On 3/25/2025 12:40 PM, olcott wrote:
>>>> On 3/25/2025 10:17 AM, dbush wrote:
>>>>> On 3/25/2025 11:13 AM, olcott wrote:
>>>>>> On 3/25/2025 10:02 AM, dbush wrote:
>>>>>>> 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.
>>>>>>
>>>>>> IT IS COUNTER-FACTUAL THAT A MACHINE DESCRIPTION ALWAYS
>>>>>> 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]
>>>>>
>>>>> That is not the complete description.  The complete description 
>>>>> consists of the code of III
>>>>
>>>> and the fact that EEE 
>>>
>>> Is called by III makes the code of EEE part of the fixed input, as 
>>> well as everything that EEE calls down to the OS level.
>>>
>>
>> Which is not relevant to whether or not III emulated
>> by EEE reaches its own final halt state.
>>
> 
> Which is why III emulated by EEE is not relevant.
> 

When the question is:
Does III emulated by EEE reach its final halt state
when III defines a pathological relationship with its emulator?

This <is> relevant because DD emulated by HHH is isomorphic
to III emulated by HHH.

int DD()
{
   int Halt_Status = HHH(DD);
   if (Halt_Status)
     HERE: goto HERE;
   return Halt_Status;
}

Then the question becomes does the DD input to HHH
specify behavior that reaches the final halt state of DD?

Here the program-under-test is what is examined
and the test program's behavior is irrelevant.

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