Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Mikko 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