Sujet : Re: How to write a self-referencial TM?
De : polcott333 (at) *nospam* gmail.com (olcott)
Groupes : comp.theoryDate : 16. May 2025, 16:40:29
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <1007m9e$3qb7l$17@dont-email.me>
References : 1 2 3 4 5 6 7 8
User-Agent : Mozilla Thunderbird
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.
}
-- Copyright 2025 Olcott "Talent hits a target no one else can hit; Geniushits a target no one else can see." Arthur Schopenhauer
How to write a self-referencial TM?
Re: How to write a self-referencial TM?
