Path: 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:27:05 +0300
Organization: -
Lines: 58
Message-ID: <1006pc9$3ld84$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> <05e306f20fcb7c88c497e353aaecd36b30fc752a.camel@gmail.com> <10053hb$3759k$1@dont-email.me> <10055rn$37m1t$1@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:27:06 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="1dfa167546830b8917680f44790d20f0";
	logging-data="3847428"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/1qIOaAvq0GZfKtipCqts5"
User-Agent: Unison/2.2
Cancel-Lock: sha1:JndK/vJQD59WMgHRMARbWh0lPqo=

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.

-- 
Mikko