Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.theory
Subject: Re: Turing Machine computable functions apply finite string
 transformations to inputs
Date: Mon, 28 Apr 2025 17:38:09 +0100
Organization: Fix this later
Lines: 47
Message-ID: <vuoath$3ljma$1@dont-email.me>
References: <vu6lnf$39fls$2@dont-email.me> <vua9oi$2lub6$1@dont-email.me>
 <vudkah$1ona3$1@dont-email.me> <vufi61$3k099$1@dont-email.me>
 <vugddv$b21g$2@dont-email.me>
 <0a2eeee6cb4b6a737f6391c963386745a09c8a01@i2pn2.org>
 <vugvr3$pke9$8@dont-email.me>
 <4818688e0354f32267e3a5f3c60846ae7956bed2@i2pn2.org>
 <vuj18i$2lf64$6@dont-email.me>
 <f0d3f2e87d9a4e0b0f445f60a33d529f41a4fcf7@i2pn2.org>
 <vuj55m$2lf64$10@dont-email.me> <vuj8h3$2uahf$3@dont-email.me>
 <vujfuu$35hcg$1@dont-email.me>
 <65dddfad4c862e6593392eaf27876759b1ed0e69@i2pn2.org>
 <vujlj0$3a526$1@dont-email.me> <vujln7$32om9$8@dont-email.me>
 <vujmmm$3a526$2@dont-email.me> <vujmrj$32om9$9@dont-email.me>
 <vujtcb$3gsgr$1@dont-email.me> <vuju44$3hnda$1@dont-email.me>
 <vuk47o$3qkbb$1@dont-email.me> <vuk6b6$3l184$1@dont-email.me>
 <vuls34$1bf1j$4@dont-email.me> <vun87k$2m24h$2@dont-email.me>
 <vunb06$2fjjl$5@dont-email.me> <vuo57j$3h5l9$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 28 Apr 2025 18:38:10 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="5ec6b2a55f0a6c1e0abdb1bc19cf1947";
	logging-data="3854026"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18NQ265xT+YwkvDLbqGdtRr0OdK4IShbLsgQg6p9Rkwmg=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:tWCK2VUrZ+av4FOPki6Z9mwca1M=
In-Reply-To: <vuo57j$3h5l9$2@dont-email.me>
Content-Language: en-GB
Bytes: 3819

On 28/04/2025 16:01, olcott wrote:
> On 4/28/2025 2:33 AM, Richard Heathfield wrote:
>> On 28/04/2025 07:46, Fred. Zwarts wrote:
>>
>> <snip>
>>
>>> So we agree that no algorithm exists that can determine for 
>>> all possible inputs whether the input specifies a program that 
>>> (according to the semantics of the machine language) halts 
>>> when directly executed.
>>> Correct?
>>
>> Correct. We can, however, construct such an algorithm just as 
>> long as we can ignore any input we don't like the look of.
>>
> 
> The behavior of the direct execution of DD cannot be derived
> by applying the finite string transformation rules specified
> by the x86 language to the input to HHH(DD). This proves that
> this is the wrong behavior to measure.
> 
> It is the behavior THAT IS derived by applying the finite
> string transformation rules specified by the x86 language
> to the input to HHH(DD) proves that THE EMULATED DD NEVER HALTS.

The x86 language is neither here nor there. What matters is 
whether a TM can be constructed that can accept an arbitrary TM 
tape P and an arbitrary input tape D and correctly calculate 
whether, given D as input, P would halt. Turing proved that such 
a TM cannot be constructed.

This is what we call the Halting Problem.

Whatever you think you've proved, you haven't solved the Halting 
Problem. There are *no* solutions. We know this because there is 
a simple well-known proof. So the only way to devise a solution 
is to re-define the problem.

And that's fine. If that's what floats your boat, you can 
re-define it as much as you like. But any proofs you may devise 
apply not to the Halting Problem but to the Olcott problem.
  --
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within