Re: How to write a self-referencial TM?

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.