Re: Turing Machine computable functions MUST apply finite string transformations to inputs

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.