Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!news.quux.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Halt Deciders must be computable functions --- dbush was always
 wrong
Date: Tue, 25 Mar 2025 21:42:39 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <eeecc1aa92b4d6e5c6825df6bbf59ed12e5db48b@i2pn2.org>
References: <vr1shq$1qopn$1@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> <vr9udn$m4cu$3@dont-email.me>
 <vr9utm$qp25$1@dont-email.me> <vr9vqm$6dfe$1@dont-email.me>
 <vra0rj$s8bo$1@dont-email.me> <vra1qb$6dfe$2@dont-email.me>
 <vra6lc$11p12$1@dont-email.me> <vra6t7$6dfe$3@dont-email.me>
 <vraci2$16s8e$1@dont-email.me> <vrad2v$6dfe$4@dont-email.me>
 <vrae5c$16s8e$2@dont-email.me> <vraec6$6dfe$5@dont-email.me>
 <vrafln$16s8e$3@dont-email.me> <vrafrv$6dfe$6@dont-email.me>
 <vrahld$16s8e$4@dont-email.me> <vrai2i$6dfe$7@dont-email.me>
 <vrapae$1hild$1@dont-email.me> <vrju06$1p5m7$1@dont-email.me>
 <vrjuti$1ph95$1@dont-email.me> <vrk0cl$1qle0$1@dont-email.me>
 <vrmj54$6grp$1@dont-email.me> <vrmm1n$5bpl$6@dont-email.me>
 <vrolfd$23fvd$1@dont-email.me> <vrppnr$34p5p$1@dont-email.me>
 <vrr3f6$ev4l$1@dont-email.me> <vrrpod$11a56$5@dont-email.me>
 <vrtt8d$31qla$1@dont-email.me> <vru879$38ob9$5@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 26 Mar 2025 01:42:55 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="1768182"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
In-Reply-To: <vru879$38ob9$5@dont-email.me>
Content-Language: en-US
X-Spam-Checker-Version: SpamAssassin 4.0.0

On 3/25/25 8:40 AM, olcott wrote:
> On 3/25/2025 4:33 AM, Mikko wrote:
>> On 2025-03-24 14:21:01 +0000, olcott said:
>>
>>> On 3/24/2025 3:00 AM, Mikko wrote:
>>>> On 2025-03-23 20:08:25 +0000, olcott said:
>>>>
>>>>> On 3/23/2025 4:49 AM, Mikko wrote:
>>>>>> On 2025-03-22 15:47:03 +0000, olcott said:
>>>>>>
>>>>>>> On 3/22/2025 9:57 AM, Mikko wrote:
>>>>>>>> On 2025-03-21 15:25:09 +0000, olcott said:
>>>>>>>>
>>>>>>>>> On 3/21/2025 10:00 AM, olcott wrote:
>>>>>>>>>> On 3/21/2025 9:44 AM, dbush wrote:
>>>>>>>>>>> On 3/17/2025 11:29 PM, olcott wrote:
>>>>>>>>>>>> On 3/17/2025 8:25 PM, dbush wrote:
>>>>>>>>>>>>> On 3/17/2025 9:18 PM, olcott wrote:
>>>>>>>>>>>>>> On 3/17/2025 7:48 PM, dbush wrote:
>>>>>>>>>>>>>>> On 3/17/2025 8:44 PM, olcott wrote:
>>>>>>>>>>>>>>>> On 3/17/2025 7:22 PM, dbush wrote:
>>>>>>>>>>>>>>>>> On 3/17/2025 8:18 PM, olcott wrote:
>>>>>>>>>>>>>>>>>> On 3/17/2025 7:00 PM, dbush wrote:
>>>>>>>>>>>>>>>>>>> On 3/17/2025 7:51 PM, olcott wrote:
>>>>>>>>>>>>>>>>>>>> On 3/17/2025 5:15 PM, dbush wrote:
>>>>>>>>>>>>>>>>>>>>> On 3/17/2025 6:10 PM, olcott wrote:
>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>> The halt decider does not and cannot possibly
>>>>>>>>>>>>>>>>>>>>>> compute the mapping from the actual behavior
>>>>>>>>>>>>>>>>>>>>>> of an executing process.
>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>> No one claimed it should.  What it must do is 
>>>>>>>>>>>>>>>>>>>>> determine what would happen in the hypothetical 
>>>>>>>>>>>>>>>>>>>>> case that a direct execution is done.
>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>> It can only do that when it assumes that the behavior
>>>>>>>>>>>>>>>>>>>> specified by the semantics of its input machine 
>>>>>>>>>>>>>>>>>>>> language
>>>>>>>>>>>>>>>>>>>> exactly matches this behavior. Its only basis is this
>>>>>>>>>>>>>>>>>>>> input finite string.
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> i.e. the semantics of the x86 language when those 
>>>>>>>>>>>>>>>>>>> actual instructions are actually executed on an 
>>>>>>>>>>>>>>>>>>> actual x86 processor.
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> A termination analyzer has no access to that.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> The input is required to be a complete description of 
>>>>>>>>>>>>>>>>> the program that can be used to determine its full 
>>>>>>>>>>>>>>>>> behavior.  In the case of DD, that description is the 
>>>>>>>>>>>>>>>>> code of the function DD, the code of the function HHH, 
>>>>>>>>>>>>>>>>> and everything that HHH calls down to the OS level.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> It does do that and this behavior does specify
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Halting behavior when executed directly, which is what is 
>>>>>>>>>>>>>>> to be reported on as per the requirements:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> It has always been incorrectly assumed that the input
>>>>>>>>>>>>>> finite string is a perfect proxy for the behavior
>>>>>>>>>>>>>> of the direct execution.
>>>>>>>>>>>>>
>>>>>>>>>>>>> False.  The input finite string is REQUIRED to be a perfect 
>>>>>>>>>>>>> proxy for direct execution, as per the requirements:
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> It looks like you simply don't understand that a
>>>>>>>>>>>> counter-factual requirement is necessarily incorrect.
>>>>>>>>>>>
>>>>>>>>>>> Category error.  Requirements can't be false.  They can 
>>>>>>>>>>> however be impossible to satisfy.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> When the definition of a [HALT decider] contradicts the 
>>>>>>>>>> definition of a [decider] in the same field of inquiry at 
>>>>>>>>>> least one of them is incorrect.
>>>>>>>>
>>>>>>>> No, there is nothing incorrect there. It simply means a halpt 
>>>>>>>> decider
>>>>>>>> is not a decider,
>>>>>>>
>>>>>>> It has always been stipulated that a [halt decider] is a type
>>>>>>> of [decider]. This means that every halt decider only has the
>>>>>>> behavior that its finite string input specifies as its only basis.
>>>>>>
>>>>>> No, it has not. "Halting decider" can be defined without mentioning
>>>>>> "decider" and some authors do so.
>>>>>
>>>>> I forgot that the notion of computable function already proves my 
>>>>> point
>>>>
>>>> Maybe, if you have a point. But it does not prove your false claim 
>>>> above.
>>>
>>> No Turing Machine computation can report on the behavior
>>> of any directly executing Turing Machine because no directly
>>> executing Turing machine is a finite string input.
>>>
>>>   given an input of the function domain it
>>>   can return the corresponding output.
>>> https://en.wikipedia.org/wiki/Computable_function
>>
>> Ia that your "point"? At least that was not what you were talking about
>> when you falsely claimed that "It has always been stipulated that a 
>> [halt decider] is a type of [decider]" and is therefore irrelevant to 
>> that
>> message and the discussion after that.
>>
> 
> A halt decider <is> and has always been a type of decider.
> The nothing of computable function  proves my point another way.
> 
> All Turing computable functions compute the mapping from an
> input finite string on the basis of something that this finite
> string specifies. No TM every has any psychic ability.
> 
> 

Right, but to be the <Foo> decider (like a Halt Decider) the mapping 
they compute has to match the <Foo?> mapping.

The Halt Mapping is DEFINED as the mapping of a program (or its 
representation) to whether that machine will halt or not.

Part of the question is whether this forms a computable function, there 
is no presumption that it is, that is the actual prime question.

Turing Machine can only compute the computable mappings, so if no Turing 
Machine exists that can compute it, that just means the mapping isn't 
computable.

This is EXACTLY what Turing proved with his proof, that ANY Turing 
Machine will have at least one input given to it that will will map to a 
different result than the Halting mapping.

There is nothing wrong with that result, it just means that Halting is 
one of the Aleph_1 possible mappings that isn't computable with the 
Aleph_0 possible deciders.