Path: 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: Mon, 24 Mar 2025 16:18:58 -0400
Organization: A noiseless patient Spider
Lines: 95
Message-ID: <vrsenh$1d1o2$3@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: 7bit
Injection-Date: Mon, 24 Mar 2025 21:18:57 +0100 (CET)
Injection-Info: dont-email.me; posting-host="2bba31d9db6d1ce3dfa332732cba05ab";
	logging-data="1476354"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18L8D+QC+NUy09E8gKbO256"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:J7fGqNP4RwJXE1MOufJo00hQXmU=
In-Reply-To: <vrse90$1jr8u$1@dont-email.me>
Content-Language: en-US

On 3/24/2025 4:11 PM, 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.
> 

Sure it can.  Any that takes a description of a turning machine that 
halt when executed directly is correct to return 1, regardless of the 
logic used to do so.


>>
>> 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 

In other words, you explicitly agree with the Linz proof that the 
halting function is not a computable function, i.e. no algorithm H can 
compute it.


> because computable
> functions cannot possibly have directly executing Turing
> machines as their inputs.

But any mathematical function, computable or not, can take a description 
of that turning machine that specifies the exact behavior when executed 
directly, for example source code or binaries.  And any turning machine 
/ algorithm by definition gives the exact same results for the same 
input when executed directly.

> 
> 
>> (<X>,Y) maps to 0 if and only if X(Y) does not halt when executed 
>> directly
>>
>>
>