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
Date: Mon, 24 Mar 2025 17:43:14 -0500
Organization: A noiseless patient Spider
Lines: 122
Message-ID: <vrsn62$1rblu$2@dont-email.me>
References: <vr1shq$1qopn$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> <vrsk13$1q39o$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 23:43:15 +0100 (CET)
Injection-Info: dont-email.me; posting-host="ac1d39214123a2f0a8db335464f421b3";
	logging-data="1945278"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX184BSoE5StufEORYBSe+y39"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:H10fhVL1/Usni+/JMlizr4OE7es=
X-Antivirus-Status: Clean
X-Antivirus: Norton (VPS 250324-4, 3/24/2025), Outbound message
Content-Language: en-US
In-Reply-To: <vrsk13$1q39o$1@dont-email.me>
Bytes: 6452

On 3/24/2025 4:49 PM, André G. Isaak wrote:
> 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.p
> 

Maybe when pure math objects. In every model of
computation they seem to always have inputs.
https://en.wikipedia.org/wiki/Computable_function

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

Since there is a bijection between natural numbers
and strings of decimal digits your qualification
seems vacuous.

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

A halting function need not be a decider?

In any case no computable function within any model
of computation computes the mapping from the behavior
of any other directly executing process to anything else.
*THIS MAKES THE FOLLOWING STATEMENT INCORRECT*

On 3/24/2025 12:35 PM, dbush wrote:
 > 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
 >
 >

A definition can be shown to be incorrect
when it contradicts other definitions in
the same system.

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