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

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?
Let's fix that. Let's apply finite string transformation rules to inputs to derive outputs.
Let x and y be expressed in unary, separated by a '+', and the active cell be ac. Whitespace is required and permitted *only* before x and after y.
while T[ac] == ' '
   ac++ (i.e. move right by one cell)
wend
while T[ac] != '+'
   ac++
wend
erase T[ac]
write '1' on T[ac]
while T[ac] != ' '
   ac++
wend
ac--
erase T[ac]
halt
Given the above as an input P tape, and
    111+11
as an input D tape, a halting decider could establish that this program halts with    11111    on the input tape.
But HHH(DD) can't establish any such thing, because it only knows how to look at DD. Therefore, HHH(DD) has nothing to say about the Halting Problem.
--
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