Path: 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 13:57:18 -0500
Organization: A noiseless patient Spider
Lines: 187
Message-ID: <vruuae$3tamc$2@dont-email.me>
References: <vr1shq$1qopn$1@dont-email.me> <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> <vruogg$3n7k6$3@dont-email.me>
 <vruosq$3hle3$7@dont-email.me> <vrusi1$3tamc$1@dont-email.me>
 <vrut66$3hle3$8@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 19:57:19 +0100 (CET)
Injection-Info: dont-email.me; posting-host="28b8eab6d237e557af892b2ab104f6c1";
	logging-data="4106956"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18ddsLvhZIOyt4LHr2qBAX2"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:ESZoeggof69s+ZJvl7xvhb1u11g=
X-Antivirus-Status: Clean
X-Antivirus: Norton (VPS 250325-18, 3/25/2025), Outbound message
Content-Language: en-US
In-Reply-To: <vrut66$3hle3$8@dont-email.me>

On 3/25/2025 1:37 PM, dbush wrote:
> On 3/25/2025 2:27 PM, olcott wrote:
>> On 3/25/2025 12:24 PM, dbush wrote:
>>> On 3/25/2025 1:18 PM, olcott wrote:
>>>> 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?
>>>>
>>>
>>>
>>> But that's not the question.  The question is whether or not an H 
>>> exists that behaves as described below:
>>>
>>
>> Did you ever bother to notice the title of this thread?
>>
>> Turing machines are only capable operating on input
>> finite strings. 
> 
> And those finite strings can be a complete description of a turing machine
> 

The input to a Turing machine cannot possibly be
the actual behavior of any executing process.

A Turing machine can only port on the behavior that a
finite string input specifies.

>> Turing machine computable functions cannot
>> compute anything that their input doesn't specify.
> 
> Translation: algorithms only compute what they're programed to compute.
> 

NO WRONG. Turing machine computable functions cannot
compute any mapping from anything that their input DOES NOT SAY.
THEIR INPUT CANNOT POSSIBLY SAY THE ACTUAL BEHAVIOR OF ANY
EXECUTING PROCESS

> And the algorithm your EEE is computing is not the mathematical halting 
> function, which has proven to not be computable:
> 

When HHH rejects DD as specifying a computation
that does not reach its final halt state HHH IS CORRECT.

> 
> Given any algorithm (i.e. a fixed immutable sequence of instructions) X 
> described as <X> with input Y:
> 
> A solution to the halting problem is an algorithm H that computes the 
> following mapping:
> 
> (<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
> (<X>,Y) maps to 0 if and only if X(Y) does not halt when executed directly
> 
> 
>>
>> THEIR INPUT NEVER SPECIFIES THE ACTUAL BEHAVIOR OF ANY
>> OTHER TURING MACHINE
========== REMAINDER OF ARTICLE TRUNCATED ==========