Path: ...!weretis.net!feeder9.news.weretis.net!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Turing Machine computable functions MUST apply finite string
 transformations to inputs
Date: Thu, 1 May 2025 07:33:20 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <c0172e5e43dc8d7ad9953aca3263a5b7d1d46635@i2pn2.org>
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>
 <2430d330090ee702268894ff281eb444dc6a6a46@i2pn2.org>
 <vuutca$1s83v$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 1 May 2025 11:47:37 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="2669065"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
In-Reply-To: <vuutca$1s83v$3@dont-email.me>
Content-Language: en-US
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 5597
Lines: 111

On 5/1/25 12:30 AM, olcott wrote:
> On 4/30/2025 6:52 PM, Richard Damon wrote:
>> On 4/30/25 6:09 PM, 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).
>>>
>>
>> And there is no requirement that a Turing Machine, or a Function, 
>> actually use its input.
>>
> 
> Computable functions are the basic objects of study in
> computability theory. Computable functions are the
> formalized analogue of the intuitive notion of algorithms,
> in the sense that a function is computable if there exists
> an algorithm that can do the job of the function, i.e.
> *given an input of the function domain it can return the*
> *corresponding output*
> https://en.wikipedia.org/wiki/Computable_function

Right, and the study is whether or not given Functions are in fact 
Computable.

Note, the above definition of a Computable Function makes it clear that 
not all functions are Computable, as they are only computable if such an 
algorithm can be found.

> 
> Then the relation between the input and the output
> is violated.
> 

Which relation?

The above definitions talks about the domain of the Function itself, 
which is the specified mapping of input to output, with no requirement 
on how that mapping was specifed.

And then there is the mapping generated by the algorithm, which only 
makes the Function computable if its output matches the above mapping 
for all input.

Only the latter is restricted by the finite string manipulation ability 
of the alogrithm. There is nothing wrong by that definition for a 
Function to be specified based on something else.

The Function only becomes Computable, if we can find an algorithm that 
implements it.

The key fact you seem to have missed is that when a Function is 
specified, it isn't necessarily Computable. This is illustrated by the 
Halting Funtion, which maps program/input pairs to Halting or 
Not-Halting based on their behavior when run.

These can be given to Turing Machines via the ability to represent all 
programs as finite strings, and we can try to see if the TM can figure 
out, in finite time, that behavior specified by that input, which *IS* 
what that program does when it is run,

A simple fact that seems to be above your ability to understand.

> 
> 
>> Note sum(2,3) isn't a Function, it is an invocation of a Function.
>>
>> You seem to have a lot of misunderstanding about the meaning of the 
>> words you use.
> 
>