Path: ...!eternal-september.org!feeder2.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: The philosophy of computation reformulates existing ideas on a new basis
Date: Wed, 13 Nov 2024 12:54:14 +0200
Organization: -
Lines: 138
Message-ID: <vh20gm$25pto$1@dont-email.me>
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: Wed, 13 Nov 2024 11:54:14 +0100 (CET)
Injection-Info: dont-email.me; posting-host="b40e0e76b399bd75dade44d820e2a1c7";
	logging-data="2287544"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19Pxs6ctGTjKPCI5+F3E13H"
User-Agent: Unison/2.2
Cancel-Lock: sha1:5ym5j8DZMGLa79Ks5949E3vuVYM=
Bytes: 7719

On 2024-11-12 22:45:10 +0000, olcott said:

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

You have also talked about x86, so it is better to include that.

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

You may call it "only normal termitaion" but there are other terminations
that need not be called "normal".

> 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 in the same category as the "aboting" your HHH may do with
certain inputs. The program does specify a next action but the
specified action is not performed.

> That is just not what is meant by halting. In software
> engineering terms "halting" is only normal termination.

No, it is not. I have worked with software enginees so much that I know
that they don't identify halting with normal termination. And also that
they are not always ssystematic and consistent with their words.

-- 
Mikko