Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: dbush <dbush.mobile@gmail.com>
Newsgroups: comp.theory
Subject: Re: Turing computable functions
Date: Tue, 25 Mar 2025 15:32:52 -0400
Organization: A noiseless patient Spider
Lines: 63
Message-ID: <vrv0d4$3hle3$10@dont-email.me>
References: <vruvsn$3tamc$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 25 Mar 2025 20:32:52 +0100 (CET)
Injection-Info: dont-email.me; posting-host="558cb3f1e92ebc1bf3f45b6c0d288267";
	logging-data="3724739"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/XHZXD17kc0wEtUWJZu9em"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:RFpPYf3W9diHSpj5rXtVWlAB/8E=
Content-Language: en-US
In-Reply-To: <vruvsn$3tamc$3@dont-email.me>
Bytes: 2855

On 3/25/2025 3:24 PM, olcott wrote:
> Cannot possibly derive any outputs not computed from
> their inputs.

Correct, algorithms can only compute computable mathematical function.

> 
> A Turing machine halt decider 

Does not exist because the required mapping is not computable:


Given any algorithm (i.e. a fixed immutable sequence of instructions) X 
described as <X> with input Y:

A solution to the halting problem is an algorithm H that computes the 
following mapping:

(<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
(<X>,Y) maps to 0 if and only if X(Y) does not halt when executed directly



> cannot possibly report
> on the behavior of any directly executing process.
> No Turing machine can every do this. This has always
> been beyond what any Turing machine can ever do.


Strawman: reporting on an executing process is not a requirement.  But 
because a Turing machine will always behavior exactly the same for a 
given input, a complete description of that Turing machine fully 
specifies what would happen in the hypothetical case that such a machine 
was executed directly.


> 
> The best that any Turing machine halt decider can
> possibly do is determine the behavior that an input
> finite string specifies.
> 

In other words, a Turing machine can only compute a computable function.

And because the mathematical halting function is not computable, no 
Turing machine can compute it.


> When we make these things 100% concrete in a language
> that has been fully operational for many years...
> 
> int DD()
> {
>    int Halt_Status = HHH(DD);
>    if (Halt_Status)
>      HERE: goto HERE;
>    return Halt_Status;
> }
> 
> When an input finite string specifies a pathological
> relationship with its simulating halt decider 

Halt deciders don't exist.