Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: =?UTF-8?B?QW5kcsOpIEcuIElzYWFr?= <agisaak@gm.invalid>
Newsgroups: comp.theory
Subject: Re: Correcting the definition of the halting problem --- Computable
 functions
Date: Mon, 24 Mar 2025 15:49:23 -0600
Organization: Christians and Atheists United Against Creeping Agnosticism
Lines: 86
Message-ID: <vrsk13$1q39o$1@dont-email.me>
References: <vr1shq$1qopn$1@dont-email.me> <vr790m$2cr9u$1@dont-email.me>
 <vr7c5g$2g9ma$1@dont-email.me> <vr7lbe$2o5t3$1@dont-email.me>
 <vr8p32$3pf1l$1@dont-email.me> <vr9elt$bv13$2@dont-email.me>
 <vr9jpt$gave$2@dont-email.me> <vr9lj6$j0f0$2@dont-email.me>
 <vr9qu8$m4cu$2@dont-email.me> <vr9ttl$q57o$1@dont-email.me>
 <vr9u5m$q57o$2@dont-email.me> <vrbckn$23f4t$1@dont-email.me>
 <vrbtiq$2j07c$2@dont-email.me> <vrc3ud$2p461$1@dont-email.me>
 <vrc4nu$2m36k$5@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 24 Mar 2025 22:49:24 +0100 (CET)
Injection-Info: dont-email.me; posting-host="46866fb2f238e79d6243f17399f0584a";
	logging-data="1903928"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+/AXUYkoW+CymAfJBaltsW"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:aNfGe7/66IEES7y5nXeAMI/3+IA=
Content-Language: en-US
In-Reply-To: <vrse90$1jr8u$1@dont-email.me>
Bytes: 5219

On 2025-03-24 14:11, olcott wrote:
> On 3/24/2025 12:35 PM, dbush wrote:
>> On 3/24/2025 12:44 PM, olcott wrote:
>>> On 3/24/2025 10:14 AM, dbush wrote:
>>>> On 3/24/2025 11:03 AM, olcott wrote:
>>>>> On 3/24/2025 6:23 AM, Richard Damon wrote:
>>>>>> On 3/23/25 11:09 PM, olcott wrote:
>>>>>>> It is impossible for HHH compute the function from the direct
>>>>>>> execution of DDD because DDD is not the finite string input
>>>>>>> basis from which all computations must begin.
>>>>>>> https://en.wikipedia.org/wiki/Computable_function
>>>>>>
>>>>>> WHy isn't DDD made into the correct finite string?i
>>>>>>
>>>>>
>>>>> DDD is a semantically and syntactically correct finite
>>>>> stirng of the x86 machine language.
>>>>
>>>> Which includes the machine code of DDD, the machine code of HHH, and 
>>>> the machine code of everything it calls down to the OS level.
>>>>
>>>>>
>>>>>> That seems to be your own fault.
>>>>>>
>>>>>> The problem has always been that you want to use the wrong string 
>>>>>> for DDD by excluding the code for HHH from it.
>>>>>>
>>>>>
>>>>> DDD emulated by HHH directly causes recursive emulation
>>>>> because it calls HHH(DDD) to emulate itself again. HHH
>>>>> complies until HHH determines that this cycle cannot
>>>>> possibly reach the final halt state of DDD.
>>>>>
>>>>
>>>> Which is another way of saying that HHH can't determine that DDD 
>>>> halts when executed directly.
>>>>
>>>
>>> given an input of the function domain it can
>>> return the corresponding output.
>>> https://en.wikipedia.org/wiki/Computable_function
>>>
>>> Computable functions are only allowed to compute the
>>> mapping from their input finite strings to an output.
>>>
>>
>>
>> The HHH you implemented is computing *a* computable function, but it's 
>> not computing the halting function:
>>
> 
> The whole point of this post is to prove that
> no Turing machine ever reports on the behavior
> of the direct execution of another Turing machine.
> 
>>
>> 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
> 
> Cannot possibly be a computable function because computable
> functions cannot possibly have directly executing Turing
> machines as their inputs.

Computable functions don't have inputs. They have domains. Turing 
machines have inputs.

While the inputs to TMs are restricted to strings, there is no such such 
restriction on computable functions. The vast majority of computable 
functions of interest do *not* have strings as their domains, yet they 
remain computable functions (a simple example would be the parity 
function which maps NATURAL NUMBERS (not strings) to yes/no values.)

You really need to learn the difference between a Halt decider and the 
halting function. They are distinct things.

André

-- 
To email remove 'invalid' & replace 'gm' with well known Google mail 
service.