Sujet : Re: How to write a self-referencial TM?
De : mikko.levanto (at) *nospam* iki.fi (Mikko)
Groupes : comp.theoryDate : 17. May 2025, 10:02:56
Autres entêtes
Organisation : -
Message-ID : <1009jc0$ajde$1@dont-email.me>
References : 1 2 3 4 5 6 7 8 9 10
User-Agent : Unison/2.2
On 2025-05-16 15:44:49 +0000, olcott said:
On 5/16/2025 2:40 AM, Mikko wrote:
On 2025-05-15 19:15:32 +0000, olcott said:
On 5/15/2025 1:49 PM, wij wrote:
On Thu, 2025-05-15 at 17:08 +0100, 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.
People used to say UTM can simulate all TM. I was questing such a UTM.
Because you said "Every UTM ...", so what is the source of such UTM?
The TM description language is more accurately
referred to as the TM specification language.
Not really. The terms "description language" and "specification language"
refer to differenct uses of the languages, not ingerently different
languages. A specification may omit details that a description must
not omit but the choice of such details must a choice of the specifier
and not forced by the language.
The term "specification" typically means all of the relevant details.
What is relevant depends on purpose.
The term "description" typically means some of the details.
Typically the relevant ones.
-- Mikko
How to write a self-referencial TM?
Re: How to write a self-referencial TM?
