Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: dbush <dbush.mobile@gmail.com>
Newsgroups: comp.theory
Subject: Re: Turing Machine computable functions MUST apply finite string
 transformations to inputs
Date: Wed, 30 Apr 2025 23:55:01 -0400
Organization: A noiseless patient Spider
Lines: 113
Message-ID: <vuural$1dekm$5@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 01 May 2025 05:55:01 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="7f5b81f1e3771b63e4016ac43992f172";
	logging-data="1489558"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18+Nq5ynmRDGHxirmicPp9x"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:+xMJGt/VPiBL/w4Qpa+8znRjPA8=
In-Reply-To: <vuur2n$1qe3m$2@dont-email.me>
Content-Language: en-US

On 4/30/2025 11:50 PM, olcott wrote:
> On 4/30/2025 7:17 PM, André G. Isaak wrote:
>> On 2025-04-30 16:09, olcott wrote:
>>> On 4/30/2025 2:55 PM, dbush wrote:
>>>> On 4/30/2025 1:32 PM, olcott wrote:
>>>>> On 4/30/2025 11:11 AM, Richard Heathfield wrote:
>>>>>> On 30/04/2025 16:44, joes wrote:
>>>>>>> Am Wed, 30 Apr 2025 10:09:45 -0500 schrieb olcott:
>>>>>>>> On 4/29/2025 5:01 AM, Mikko wrote:
>>>>>>>
>>>>>>>>> Irrelevant. There is sufficient agreement what Turing machines 
>>>>>>>>> are.
>>>>>>>>
>>>>>>>> Turing machine computable functions must apply finite string
>>>>>>>> transformation rues to inputs to derive outputs.
>>>>>>>>
>>>>>>>> This is not a function that computes the sum(3,2):
>>>>>>>> int sum(int x, int y) { return 5; }
>>>>>>> Yes it is, for all inputs.
>>>>>>
>>>>>> Not much of a computation, though, is it?
>>>>>>
>>>>>
>>>>> It IS NOT a Turing Computable function
>>>>
>>>> Lying by misuse of terms.
>>>>
>>>> A turing computable function is a mapping for which an algorithm 
>>>> exists to compute it, not the algorithm itself.
>>>>
>>>> Further use of "turing computable function" when what is meant is 
>>>> "algorithm" will result in the former being replaced with the later 
>>>> in future responses to your posts to make it clear what you are 
>>>> actually talking about.
>>>>
>>>>
>>>>> because it does not ever apply any finite
>>>>> string transformation  rules to its inputs.
>>>>
>>>> Sure it does.  It computes the mapping of all pairs of integers to 
>>>> the number 5.
>>>>
>>>
>>> int sum(int x, int y) { return 5; }
>>> Does not apply transformations to its inputs
>>> to derive its outputs thus is no kind of computable
>>> function not even for sum(2,3).
>>
>> 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; }

False.  It computes this function:


For all integers X and Y:

(X,Y) maps to 5

> 
>> [I won't call that function 'sum()' because that would be misleading, 
>> but the the *name* assigned to a C function has no necessary relation 
>> to the function it computes. It's good programming practice to give 
>> functions descriptive names but nothing in the C standard requires it).
>>
>> You keep conflating C functions/Turing Machines with computable 
>> functions and as a result come across as completely ignorant about the 
>> topic you purport to be discussing. No C function or Turing Machine is 
>> a computable function. They are ways of expressing algorithms.
>>
>> André
>>
> 
> The complete ignorance is to expect HHH(DD)
> to report on DD(DD). 

It is expected when we start with the assumption that the following 
requirements can be satisfied and HHH satisfies them.



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


When we reach a contradiction, that proves the assumption that the above 
requirements can be met is false, as shown by Linz and as you have 
*explicitly* agreed with.