Re: How to write a self-referencial TM?

On 5/15/2025 2:57 PM, wij wrote:

On Thu, 2025-05-15 at 11:47 -0500, olcott wrote:

On 5/15/2025 11:08 AM, Mike Terry wrote:

On 14/05/2025 18:53, wij wrote:

On Wed, 2025-05-14 at 12:24 -0500, olcott wrote:

On 5/14/2025 11:43 AM, wij wrote:

On Wed, 2025-05-14 at 09:51 -0500, olcott wrote:

On 5/14/2025 12:13 AM, wij wrote:

Q: Write a turing machine that performs D function (which calls
itself):
>
void D() {
     D();
}
>
Easy?
>
>

>
That is not a TM.

>
It is a C program that exists. Therefore, there must be a equivalent
TM.
>

To make a TM that references itself the closest
thing is a UTM that simulates its own TM source-code.

>
How does a UTM simulate its own TM source-code?
>

>
You run a UTM that has its own source-code on its tape.

>
What is exactly the source-code on its tape?
>

>
Every UTM has some scheme which can be applied to a (TM & input tape)
that is to be simulated.  The scheme says how to turn the (TM + input
tape) into a string of symbols that represent that computation.
>
So to answer your question, the "source-code on its tape" is the result
of applying the UTM's particular scheme to the combination (UTM, input
tape) that is to be simulated.
>
If you're looking for the exact string symbols, obviously you would need
to specify the exact UTM being used, because every UTM will have a
different answer to your question.
>
>
Mike.
>

>
These things cannot be investigated in great
depth because there is no fully encoded UTM in
any standard language.

 Sort of.
 

If there was such a UTM then examining things
like a termination analyzer would be too difficult
because of the volume of details. Even moving a
single value to a specific memory location can
take many many steps.

 So, which part of POOH is "fully encoded UTM"
 

A RASP machine
https://en.wikipedia.org/wiki/Random-access_stored-program_machine
is a much better fit for examining the details of any
complex algorithm.
>
The x86 language is essentially the same thing as a RASP
machine for all computations that can be accomplished
with the amount of memory that is available.

 Absolutely false. POOH is the example that rejected TM/RASP instead of C.
 In trying making P!=NP proof (may have defects, I just leave it there to improve)
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
I feel TM would be very long and tedious, so I claimed that no *algorithm* can
solve NPC (algorithmic) problems. (thanks to olcott, this proof was inspired in
refuting POOH.)
 See also Spu in my recent post. TM is very low-level to solve many idea of problems.
 

To be a computable function within a model of computation
a sequence of the steps of a specific algorithm must be
applied to (an often finite string) input to derive an output.
https://en.wikipedia.org/wiki/Computable_function
>
When computing the sum() function the steps of the algorithm
of arithmetic must be applied to the inputs.
>
*When computing the halt() function steps with a simulating*
*termination analyzer the behavioral steps specified by the*
*input must be simulated according to the computer language*
*of this input*
>
*I may be wrong yet it seems to me that*
Computer science never knew these things before in that
it never placed any limit on the type of algorithm that
must be performed.
>
I think that it was Ben that said that one of two
functions that do nothing besides return true or false
is correct on all of the counter-example inputs
to the halting problem.
>
When we require that a mapping be computed from an
input, then this idea is rejected.
>

 You are excellent in quoting tautology to support your claims.
 

Most people don't know that a mapping must be
computed from the inputs, hence Ben's mistake.
--
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer