Path: ...!eternal-september.org!feeder3.eternal-september.org!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Turing Machine computable functions apply finite string
 transformations to inputs
Date: Mon, 28 Apr 2025 21:35:49 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <6cb60a153593300a9b9ba911d3e38fa1d1a4840d@i2pn2.org>
References: <vu6lnf$39fls$2@dont-email.me> <vugvr3$pke9$8@dont-email.me>
 <4818688e0354f32267e3a5f3c60846ae7956bed2@i2pn2.org>
 <vuj18i$2lf64$6@dont-email.me>
 <f0d3f2e87d9a4e0b0f445f60a33d529f41a4fcf7@i2pn2.org>
 <vuj55m$2lf64$10@dont-email.me> <vuj8h3$2uahf$3@dont-email.me>
 <vujfuu$35hcg$1@dont-email.me>
 <65dddfad4c862e6593392eaf27876759b1ed0e69@i2pn2.org>
 <vujlj0$3a526$1@dont-email.me> <vujln7$32om9$8@dont-email.me>
 <vujmmm$3a526$2@dont-email.me> <vujmrj$32om9$9@dont-email.me>
 <vujtcb$3gsgr$1@dont-email.me> <vuju44$3hnda$1@dont-email.me>
 <vuk47o$3qkbb$1@dont-email.me> <vuk6b6$3l184$1@dont-email.me>
 <vuls34$1bf1j$4@dont-email.me> <vun87k$2m24h$2@dont-email.me>
 <vunb06$2fjjl$5@dont-email.me> <vuo57j$3h5l9$2@dont-email.me>
 <vuo68a$3dd6e$1@dont-email.me> <vuo782$3jn5n$2@dont-email.me>
 <vuo7jc$3dd6e$2@dont-email.me> <vuoatj$3jn5n$6@dont-email.me>
 <vuobsk$3dd6e$5@dont-email.me> <vuoif9$3td7u$3@dont-email.me>
 <vuoj0d$3dd6e$8@dont-email.me> <vuoj9n$3td7u$5@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 29 Apr 2025 02:07:43 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="2331913"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
In-Reply-To: <vuoj9n$3td7u$5@dont-email.me>
Content-Language: en-US
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 5355
Lines: 86

On 4/28/25 3:01 PM, olcott wrote:
> On 4/28/2025 1:56 PM, dbush wrote:
>> On 4/28/2025 2:47 PM, olcott wrote:
>>> On 4/28/2025 11:54 AM, dbush wrote:
>>>> On 4/28/2025 12:38 PM, olcott wrote:
>>>>> On 4/28/2025 10:41 AM, dbush wrote:
>>>>>> On 4/28/2025 11:35 AM, olcott wrote:
>>>>>>> On 4/28/2025 10:18 AM, dbush wrote:
>>>>>>>> On 4/28/2025 11:01 AM, olcott wrote:
>>>>>>>>> On 4/28/2025 2:33 AM, Richard Heathfield wrote:
>>>>>>>>>> On 28/04/2025 07:46, Fred. Zwarts wrote:
>>>>>>>>>>
>>>>>>>>>> <snip>
>>>>>>>>>>
>>>>>>>>>>> So we agree that no algorithm exists that can determine for 
>>>>>>>>>>> all possible inputs whether the input specifies a program 
>>>>>>>>>>> that (according to the semantics of the machine language) 
>>>>>>>>>>> halts when directly executed.
>>>>>>>>>>> Correct?
>>>>>>>>>>
>>>>>>>>>> Correct. We can, however, construct such an algorithm just as 
>>>>>>>>>> long as we can ignore any input we don't like the look of.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> The behavior of the direct execution of DD cannot be derived
>>>>>>>>> by applying the finite string transformation rules specified
>>>>>>>>> by the x86 language to the input to HHH(DD). This proves that
>>>>>>>>
>>>>>>>> The assumption that an H exists that meets the below 
>>>>>>>> requirements is false, as shown by Linz and others:
>>>>>>>>
>>>>>>>
>>>>>>> I have just proved that those requirements are stupidly wrong
>>>>>>
>>>>>> Category error.  The mapping exists 
>>>>>
>>>>> Computable functions are the formalized analogue
>>>>> of the intuitive notion of algorithms, in the
>>>>> sense that a function is computable if there
>>>>> exists an algorithm that can do the job of the
>>>>> function, i.e.
>>>>
>>>> i.e. a computable function is a mathematical mapping for which an 
>>>> algorithm exists to compute in.
>>>>
>>>> And the halting function below is not a computable function:
>>>>
>>>
>>> It is NEVER a computable function 
>>
>> Let The Record Show:
>>
>> That Peter Olcott has *explicitly* admitted that the halting function:
>>
>> (<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
>>
>> Is not a computable function, as Linz and others have proven, meaning 
>> he has agreed that the Linz halting theorem 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 
>>>> direct
>>
>>
>> So what are you doing to do now that you're no longer working on the 
>> halting problem?
> 
> The above ignores the requirement that Turing Computable functions
> are only allowed to derive their outputs by applying finite string
> transformations to their inputs.
> 

No it doesn't. Becuase nothing says that the Function that the Halt 
Decider is required to try to compute is a Computable Function.

So, HHH might be unable to do it, but is still required by the problem 
to do it, but that is ok, since one answer to the problem is that the 
function just isn't computable, which is what is actually proven.