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: Mon, 11 Nov 2024 13:06:46 +0200
Organization: -
Lines: 129
Message-ID: <vgsog6$uu8r$1@dont-email.me>
References: <vfli1h$fj8s$1@dont-email.me> <vfp8c0$3tobi$2@i2pn2.org> <vfpcko$1837o$3@dont-email.me> <vfpish$3u885$2@i2pn2.org> <vfpjk2$1976k$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>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 11 Nov 2024 12:06:46 +0100 (CET)
Injection-Info: dont-email.me; posting-host="88f660726df1b76a05d2b3eb8bbe5a8c";
	logging-data="1014043"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+2tOzTaR7PAVBHsS2iyceb"
User-Agent: Unison/2.2
Cancel-Lock: sha1:xS+TS9XpXW7GRaS6u99fzvjzcTU=
Bytes: 6942

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.

>>> The halting problem has always been about whether a finite
>>> string input specifies a computation that will reach its
>>> final halt state.
>>> 
>>> If you disagree then you must provide a complete and coherent
>>> counter-example conclusively proving otherwise not merely
>>> some vague reference to some other things somewhere else.
>> 
>> From https://www.tutorialspoint.com/automata_theory/ 
>> turing_machine_halting_problem.htm
>> 
>>> Turing Machine Halting Problem
>>> Input − A Turing machine and an input string w.
>>> Problem − Does the Turing machine finish computing of the string w in a 
>>> finite number of steps? The answer must be either yes or no.
> 
> The computation specified by the finite string DDD
> emulated by HHH cannot possibly reach its "return"
> instruction final halt state.

It can and does if HHH is a decider and otherwise does not matter.

> The computation specified by the finite string DDD
> emulated by HHH1 IS NOT THE ACTUAL INPUT TO HHH.

HHH1 can take same inputs as HHH. These inputs specify some behaviour.
What they do with this input may differ.

> HHH must compute the mapping FROM ITS INPUT TO THE
> BEHAVIOR THAT THIS INPUT SPECIFIES.

Not to full behaviour but to one feature of that behaviour.
Doesn't HHH1 need to?

-- 
Mikko