Re: How to write a self-referencial TM?

Op 16.mei.2025 om 17:40 schreef olcott:

On 5/16/2025 2:27 AM, Mikko wrote:

On 2025-05-15 16:47:49 +0000, olcott said:
>

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.

>
Investigations do not need a standard language. For an investigation an
ad hoc language is good enough and usually better.
>

 Until I made this concrete people kept assuming that
an input DD could be defined that actually does the
opposite of whatever value that its simulating termination
analyzer HHH returns.
 int main()
{
   DD(); // HHH cannot report on the behavior of its caller.
}
 

HHH cannot simulate itself. It is programmed to do a wild guess about its own behaviour. Therefore, it produces false negatives. It reports non-halting when it halts:
        int main() {
          return HHH(main);
        }