Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: How to write a self-referencial TM?
Date: Fri, 16 May 2025 10:24:19 +0300
Organization: -
Lines: 32
Message-ID: <1006p73$3lci3$1@dont-email.me>
References: <1e4f1a15826e67e7faf7a3c2104d09e9dadc6f06.camel@gmail.com> <1002akp$2i4bk$2@dont-email.me> <479eebef3bd93e82c8fe363908b254b11d15a799.camel@gmail.com> <1002jkk$2k00a$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 16 May 2025 09:24:20 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="1dfa167546830b8917680f44790d20f0";
	logging-data="3846723"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX189GLRX/EeKC8dspJr900Hm"
User-Agent: Unison/2.2
Cancel-Lock: sha1:nWMJXom41/8s4aSY88LQE10wmiY=
Bytes: 1883

On 2025-05-14 17:24:36 +0000, olcott said:

> 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.

A UTM requires a translation to its input language. A source code cannot
be used unless it happens to be written in the UTM's input language.

-- 
Mikko