Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.theory
Subject: Re: Functions computed by Turing Machines MUST apply finite string
 transformations to inputs
Date: Fri, 2 May 2025 05:03:26 +0100
Organization: Fix this later
Lines: 153
Message-ID: <vv1g6e$7i0c$1@dont-email.me>
References: <TuuNP.2706011$nb1.2053729@fx01.ams4>
 <87cyd5182l.fsf@nosuchdomain.example.com> <vu6lnf$39fls$2@dont-email.me>
 <vugddv$b21g$2@dont-email.me> <vui4uf$20dpc$1@dont-email.me>
 <vuivtb$2lf64$3@dont-email.me> <vungtl$2v2kr$1@dont-email.me>
 <vuoaac$3jn5n$5@dont-email.me> <vuq81v$1hjka$1@dont-email.me>
 <vutefq$gmbi$3@dont-email.me>
 <991dde3a60e1485815b789520c7149e7842d18f2@i2pn2.org>
 <vuti3c$jq57$1@dont-email.me> <vutmr6$nvbg$2@dont-email.me>
 <vutv7r$v5pn$4@dont-email.me> <vuu73m$151a8$3@dont-email.me>
 <vuuej8$1cqp7$1@dont-email.me> <vuur2n$1qe3m$2@dont-email.me>
 <vv0352$2ur4q$1@dont-email.me> <vv0kpi$3djh5$1@dont-email.me>
 <vv13ro$3r3ei$1@dont-email.me> <vv160a$3smj7$1@dont-email.me>
 <vv18s7$3uer0$1@dont-email.me> <vv1b03$4a4k$2@dont-email.me>
 <vv1bav$3ra6l$7@dont-email.me> <vv1frt$97hp$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 02 May 2025 06:03:27 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="3a1c0b2ab3dc637eeb67dc4cd879a061";
	logging-data="247820"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX192BcJbHJ/BVUQFHbZg2+YBkoyQSZBf99s+cGIHh+1ZPg=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:OCrueZyxX9iOXOOGG6qBGQbUKKM=
Content-Language: en-GB
In-Reply-To: <vv1frt$97hp$1@dont-email.me>

On 02/05/2025 04:57, olcott wrote:
> On 5/1/2025 9:40 PM, dbush wrote:
>> On 5/1/2025 10:34 PM, olcott wrote:
>>> On 5/1/2025 8:58 PM, André G. Isaak wrote:
>>>> On 2025-05-01 19:09, olcott wrote:
>>>>> On 5/1/2025 7:32 PM, André G. Isaak wrote:
>>>>>> On 2025-05-01 14:15, olcott wrote:
>>>>>>> On 5/1/2025 10:14 AM, André G. Isaak wrote:
>>>>>>>> On 2025-04-30 21:50, olcott wrote:
>>>>>>>>> On 4/30/2025 7:17 PM, André G. Isaak wrote:
>>>>>>>>
>>>>>>>>>> You are still hopelessly confused about your terminology.
>>>>>>>>>>
>>>>>>>>>> Computable functions are a subset of mathematical 
>>>>>>>>>> functions, and mathematical functions are *not* the 
>>>>>>>>>> same thing as C functions. Functions do not apply 
>>>>>>>>>> "transformations". They are simply mappings, and a 
>>>>>>>>>> functions which maps every pair of natural numbers to 5 
>>>>>>>>>> is a perfectly legitimate, albeit not very interesting, 
>>>>>>>>>> function.
>>>>>>>>>>
>>>>>>>>>> What makes this function a *computable function* is 
>>>>>>>>>> that fact that it is possible to construct a C function 
>>>>>>>>>> (or a Turing Machine, or some other type of algorithm) 
>>>>>>>>>> such as int foo(int x, int y) {return 5;} which 
>>>>>>>>>> computes that particular function; but the C function 
>>>>>>>>>> and the computable function it computes are entirely 
>>>>>>>>>> separate entities.
>>>>>>>>>
>>>>>>>>> computes the sum of two integers
>>>>>>>>> by transforming the inputs into an output.
>>>>>>>>> int sum(int x, int y) { return x + y; }
>>>>>>>>>
>>>>>>>>> Computes no function because it ignores its inputs.
>>>>>>>>> int sum(int x, int y) { return 5; }
>>>>>>>>
>>>>>>>> All you're demonstrating here is that you have no clue 
>>>>>>>> what a function is, nor, apparently, do you have any 
>>>>>>>> desire to learn.
>>>>>>>>
>>>>>>>> André
>>>>>>>>
>>>>>>>
>>>>>>> What I am explaining is that a halt decider
>>>>>>> must compute the mapping FROM THE INPUTS ONLY
>>>>>>> by applying a specific set of finite string
>>>>>>> transformations to the inputs.
>>>>>>
>>>>>> No. Halt deciders weren't even mentioned above. I was 
>>>>>> addressing your absurd claim that int foo(int x, int y) { 
>>>>>> return 5; } does not compute a function. This clearly 
>>>>>> indicates that you do not grasp the concept of "function".
>>>>>>
>>>>>
>>>>> This is a brand new elaboration of computer
>>>>> science that I just came up with.
>>>>
>>>> IOW something you've pulled out of your ass.
>>>>
>>>>> It is common knowledge THAT inputs must correspond
>>>>> to OUTPUTS. What is totally unknown and brand new
>>>>> created by me is HOW inputs are made to correspond
>>>>> to OUTPUTS.
>>>>
>>>> We were discussing functions. Functions don't have inputs or 
>>>> outputs; they have domains and codomains. ALGORITHMS have 
>>>> inputs and outputs, and you keep conflating the two.
>>>>
>>>>> Specific finite string transformation rules are
>>>>> applied to inputs to derive outputs.
>>>>
>>>> Please point to a definition of 'function' which mentions 
>>>> "finite string transformation rules". This may be a useful 
>>>> way of viewing some (but certainly not all) algorithms, but 
>>>> it has nothing to do with functions. Functions are simply a 
>>>> mapping from one set (the domain) to another set (the 
>>>> codomain) such that every element of the domain maps to one 
>>>> and only one element of the codomain.
>>>>
>>>>> What everyone else has been doing is simply GUESSING
>>>>> that they correspond or relying on some authority
>>>>> that say they must correspond. (Appeal to authority error).
>>>>
>>>> This is another baseless assertion that you've simply pulled 
>>>> out of your ass. If you think otherwise, please provide a 
>>>> concrete example
>>>>
>>>>> DD correctly emulated by HHH maps to NON-HALTING BEHAVIOR.
>>>>> It really does, all that you have to do is PAY ATTENTION.
>>>>
>>>> Whether DD emulated by HH maps to halting or non-halting 
>>>> behaviour is entirely dependent on which function is being 
>>>> computed.
>>>>
>>>> André
>>>>
>>>
>>> We are computing the halt function
>>
>> i.e. this function:
>>
>>
>> Given any algorithm (i.e. a fixed immutable sequence of 
>> instructions) X described as <X> with input Y:
>>
>> (<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
>>
>>
>> Which has been proven to be uncomputable, as shown by Linz and 
>> as you have *explicitly* agreed is correct.
>>
>>> FOR THE INPUT NOT ANY DAMN THING ELSE
>>> FOR THE INPUT NOT ANY DAMN THING ELSE
>>> FOR THE INPUT NOT ANY DAMN THING ELSE
>>> FOR THE INPUT NOT ANY DAMN THING ELSE
>>>
>>> FINITE STRING TRANSFORMATIONS OF THE INPUT ELSE WRONG
>>> FINITE STRING TRANSFORMATIONS OF THE INPUT ELSE WRONG
>>> FINITE STRING TRANSFORMATIONS OF THE INPUT ELSE WRONG
>>>
>>> int DD()
>>> {
>>>    int Halt_Status = HHH(DD);
>>>    if (Halt_Status)
>>>      HERE: goto HERE;
>>>    return Halt_Status;
>>> }
>>>
>>> Replacing the code of HHH with an unconditional simulator and 
>>> subsequently running HHH(DD) specifies recursive
>>> simulation such that DD cannot possibly reach its
>>> "return instruction" (final halt state). Thus HHH
>>> is correct to reject DD as non halting.
>>
>> So you changed the input.  Changing the input is not allowed.
>>
> 
> I never changed the input.

DD calls HHH. If you indulge in "Replacing the code of HHH" you 
necessarily change the behaviour of DD. DD is an input. Ergo, you 
changed the input.

<snip>

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