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: Tue, 29 Oct 2024 09:57:29 +0200
Organization: -
Lines: 46
Message-ID: <vfq4h9$1fo1n$1@dont-email.me>
References: <vfli1h$fj8s$1@dont-email.me> <vflue8$3nvp8$2@i2pn2.org> <vfmd8m$k2m7$1@dont-email.me> <bcd82d9f8a987d3884220c0df7b8f7204cb9de3e@i2pn2.org> <vfmueh$mqn9$1@dont-email.me> <ff039b922cabbb6d44f90aa71a52d8c2f446b6ab@i2pn2.org> <vfo95k$11qs1$1@dont-email.me> <vfp8c0$3tobi$2@i2pn2.org> <vfpbtq$1837o$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 29 Oct 2024 08:57:30 +0100 (CET)
Injection-Info: dont-email.me; posting-host="aa649741e7f9f782e768cc0681b2fee1";
	logging-data="1564727"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/kZRsV4/WyQBOpgbU4RuVr"
User-Agent: Unison/2.2
Cancel-Lock: sha1:IzlstHZe6zWnrRBVoWt9lUwUV2E=
Bytes: 3070

On 2024-10-29 00:57:30 +0000, olcott said:

> On 10/28/2024 6:56 PM, Richard Damon wrote:
>> On 10/28/24 11:04 AM, olcott wrote:
>>> On 10/28/2024 6:16 AM, Richard Damon wrote:
>>>> The machine being used to compute the Halting Function has taken a 
>>>> finite string description, the Halting Function itself always took a 
>>>> Turing Machine,
>>>> 
>>> 
>>> That is incorrect. It has always been the finite string Turing Machine
>>> description of a Turing machine is the input to the halt decider.
>>> There are always been a distinction between the abstraction and the
>>> encoding.
>> 
>> Nope, read the problem you have quoted in the past.
>> 
> 
> Ultimately I trust Linz the most on this:
> 
> the problem is: given the description of a Turing machine
> M and an input w, does M, when started in the initial
> configuration qow, perform a computation that eventually halts?
> https://www.liarparadox.org/Peter_Linz_HP_317-320.pdf
> 
> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
> 
> Linz also makes sure to ignore that the behavior of ⟨Ĥ⟩ ⟨Ĥ⟩
> correctly simulated by embedded_H cannot possibly reach
> either ⟨Ĥ.qy⟩ or ⟨Ĥ.qn⟩ because like everyone else he rejects
> simulation out of hand:
> 
> We cannot find the answer by simulating the action of M on w,
> say by performing it on a universal Turing machine, because
> there is no limit on the length of the computation.

That statement does not fully reject simulation but is correct in
the observation that non-halting cannot be determied in finite time
by a complete simulation so someting else is needed instead of or
in addition to a partial simulation. Linz does include simulationg
Turing machines in his proof that no Turing machine is a halt decider.

-- 
Mikko