Path: ...!weretis.net!feeder9.news.weretis.net!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: The philosophy of computation reformulates existing ideas on a
 new basis
Date: Tue, 12 Nov 2024 18:44:29 -0500
Organization: i2pn2 (i2pn.org)
Message-ID: <d13135987ff70cfe27bb6e98351ecda99121c3d6@i2pn2.org>
References: <vfli1h$fj8s$1@dont-email.me>
 <086fc32f14bcc004466d3128b0fe585b27377399@i2pn2.org>
 <vfqsui$1jg6i$2@dont-email.me> <vft4om$44tc$2@i2pn2.org>
 <vft944$25aio$6@dont-email.me>
 <11408789ed30027f4bc9a743f353dfa9b4712109@i2pn2.org>
 <QU2dnTAfup30Rr_6nZ2dnZfqn_WdnZ2d@brightview.co.uk>
 <vfvnml$2ll12$1@dont-email.me> <vfvujg$2mcse$6@dont-email.me>
 <vg2cqm$37cq6$1@dont-email.me> <vg2kfq$38m0h$1@dont-email.me>
 <vg4va2$3ok87$1@dont-email.me> <vg55lv$3pnvp$1@dont-email.me>
 <vg7sdl$cbfk$1@dont-email.me> <vg83vt$dri5$1@dont-email.me>
 <vgcmu4$1eurt$1@dont-email.me> <vgd5vl$1hqli$1@dont-email.me>
 <vgfv31$25h28$1@dont-email.me> <vgg1qh$26126$1@dont-email.me>
 <vgi2t6$2js8i$1@dont-email.me> <vgiqgt$2nkqv$2@dont-email.me>
 <vgl0pf$37081$1@dont-email.me> <vgl7qo$37h38$3@dont-email.me>
 <vgnbfc$3uefk$1@paganini.bofh.team> <vgnt6e$3qq7s$4@dont-email.me>
 <vgsog6$uu8r$1@dont-email.me> <vgt71t$11e5a$4@dont-email.me>
 <vgvdp1$1iie3$1@dont-email.me> <vh0lpm$1qfts$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 12 Nov 2024 23:44:30 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="2189860"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
X-Spam-Checker-Version: SpamAssassin 4.0.0
In-Reply-To: <vh0lpm$1qfts$1@dont-email.me>
Content-Language: en-US
Bytes: 8359
Lines: 159

On 11/12/24 5:45 PM, olcott wrote:
> On 11/12/2024 5:22 AM, Mikko wrote:
>> On 2024-11-11 15:15:09 +0000, olcott said:
>>
>>> On 11/11/2024 5:06 AM, Mikko wrote:
>>>> On 2024-11-09 14:56:14 +0000, olcott said:
>>>>
>>>>> On 11/9/2024 3:53 AM, Mikko wrote:
>>>>>> On 2024-11-08 14:39:20 +0000, olcott said:
>>>>>>
>>>>>>> On 11/8/2024 6:39 AM, Mikko wrote:
>>>>>>>> On 2024-11-07 16:39:57 +0000, olcott said:
>>>>>>>>
>>>>>>>>> On 11/7/2024 3:56 AM, Mikko wrote:
>>>>>>>>>> On 2024-11-06 15:26:06 +0000, olcott said:
>>>>>>>>>>
>>>>>>>>>>> On 11/6/2024 8:39 AM, Mikko wrote:
>>>>>>>>>>>> On 2024-11-05 13:18:43 +0000, olcott said:
>>>>>>>>>>>>
>>>>>>>>>>>>> On 11/5/2024 3:01 AM, Mikko wrote:
>>>>>>>>>>>>>> On 2024-11-03 15:13:56 +0000, olcott said:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> On 11/3/2024 7:04 AM, Mikko wrote:
>>>>>>>>>>>>>>>> On 2024-11-02 12:24:29 +0000, olcott said:
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> HHH does compute the mapping from its input DDD
>>>>>>>>>>>>>>>>> to the actual behavior that DDD specifies and this
>>>>>>>>>>>>>>>>> DOES INCLUDE HHH emulating itself emulating DDD.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> Yes but not the particular mapping required by the 
>>>>>>>>>>>>>>>> halting problem.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Yes it is the particular mapping required by the halting 
>>>>>>>>>>>>>>> problem.
>>>>>>>>>>>>>>> The exact same process occurs in the Linz proof.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> The halting probelm requires that every halt decider 
>>>>>>>>>>>>>> terminates.
>>>>>>>>>>>>>> If HHH(DDD) terminates so does DDD. The halting problmen 
>>>>>>>>>>>>>> requires
>>>>>>>>>>>>>> that if DDD terminates then HHH(DDD) accepts as halting.
>>>>>>>>>>>>>
>>>>>>>>>>>>> void Infinite_Loop()
>>>>>>>>>>>>> {
>>>>>>>>>>>>>    HERE: goto HERE;
>>>>>>>>>>>>>    return;
>>>>>>>>>>>>> }
>>>>>>>>>>>>>
>>>>>>>>>>>>> No that is false.
>>>>>>>>>>>>> The measure is whether a C function can possibly
>>>>>>>>>>>>> reach its "return" instruction final state.
>>>>>>>>>>>>
>>>>>>>>>>>> Not in the original problem but the question whether a 
>>>>>>>>>>>> particular strictly
>>>>>>>>>>>> C function will ever reach its return instruction is equally 
>>>>>>>>>>>> hard. About
>>>>>>>>>>>
>>>>>>>>>>> It has always been about whether or not a finite string input
>>>>>>>>>>> specifies a computation that reaches its final state.
>>>>>>>>>>
>>>>>>>>>> Not really. The original problem was not a halting problem but 
>>>>>>>>>> Turing's
>>>>>>>>>
>>>>>>>>> Exactly. The actual Halting Problem was called that by Davis
>>>>>>>>> in 1952. Not the same as Turing proof.
>>>>>>>>
>>>>>>>> In early times there was variation in how things were presented 
>>>>>>>> and what
>>>>>>>> words were used. Post had studied the halting problem of his tag 
>>>>>>>> system
>>>>>>>> much earlier but didn't call it a machine. Many other problems 
>>>>>>>> were also
>>>>>>>> studied and later found to be more or less related to the halting
>>>>>>>> problem and its variants.
>>>>>>>>
>>>>>>>>> *So we are back to The Halting Problem itself*
>>>>>>>>>
>>>>>>>>> has always been about whether or not a finite string input
>>>>>>>>> specifies a computation that reaches its final state.
>>>>>>>>
>>>>>>>> No, it has been a collection of related problems that includes that
>>>>>>>> particular one.
>>>>>>>
>>>>>>> The halting problem has always been abuut halting
>>>>>>
>>>>>> Nevertheless Turing's solution to his circularity problem is usually
>>>>>> regarded as the first solution to the halting problem.
>>>>>>
>>>>>>>> As the problems are related and equally hard it does
>>>>>>>> not really matter which one you choose as long as you are clear
>>>>>>>> about your choice. To argue about the meaning of words id a clear
>>>>>>>> indcation of an intent to avoid an honest discussion.
>>>>>>
>>>>>>> It is not the meaning of words it is the semantic
>>>>>>> property of the finite string pair HHH/DDD.
>>>>>>
>>>>>> Above you have argued about the meanings of the words and
>>>>>> keep doing so below.
>>>>>
>>>>> It is the meaning of the bytes of x86 code and
>>>>> bytes of code are not words.
>>>>
>>>> No, nothing you have said tells anuything about meanings of the bytes
>>>> of x86 code. (A pair of such bytes is sometimes called a "word").
>>>> You were just arguing about the meanings the verb "halt" and other
>>>> words.
>>>
>>> Halt means reaching a final halt state to say otherwise
>>> is ignorant or dishonest.
>>
>> The exact definition of "halt" varies depending on the model.
>> For a Turing machine halting means reaching a configuration
>> where where there is no rule for the state and current symbol.
> 
> Since we are only talking about Turing Machines and C functions
> there is no need to get into other models.
> 
>> For a C program it is more ambiguous as there are situations
>> where the language standard does not specify whether the execution
>> should be terminated or continued. 
> 
> Reaching the "return" instruction final halt state <is>
> the only normal termination for a C function.

And since the actual semantic meaning of the input gets there, it is 
halting.

> 
> If you want to get silly you can say that a C function stuck
> in an infinite loop "halts" when you yank the computer's power
> cord out. That is just not what is meant by halting. In software
> engineering terms "halting" is only normal termination.
> 

Nope, but an aborted emulation doesn't make it non-halting either.

>> THere is similar ambiguity in
>> x86 semantics as there are operation codes that are defined on
>> some x86 processor models but undefined on others, and it is
>> also undefined what happens on a jump to a address in a
>> non-exstent or uninitialised memory.
>>
> 
> _DDD()
> [00002172] 55         push ebp      ; housekeeping
> [00002173] 8bec       mov ebp,esp   ; housekeeping
> [00002175] 6872210000 push 00002172 ; push DDD
> [0000217a] e853f4ffff call 000015d2 ; call HHH(DDD)
> [0000217f] 83c404     add esp,+04
> [00002182] 5d         pop ebp
> [00002183] c3         ret
> Size in bytes:(0018) [00002183]
> 
> Anyone with sufficient understanding of the x86 language
> fully well knows that no DDD emulated by any HHH can
> possibly reach past its own [0000217a] machine address.
> 
> 
>