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: Thu, 15 May 2025 10:07:54 +0300
Organization: -
Lines: 21
Message-ID: <10043sa$30qd0$1@dont-email.me>
References: <1e4f1a15826e67e7faf7a3c2104d09e9dadc6f06.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 15 May 2025 09:07:54 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="1d3ea60c43909c97d925f5b2a4bb28e2";
	logging-data="3172768"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX190gdog1LDTeBfR/OgeA2tU"
User-Agent: Unison/2.2
Cancel-Lock: sha1:Api3O7Kz+1iwW9uUXe/WlDXBLHU=

On 2025-05-14 05:13:40 +0000, wij said:

> Q: Write a turing machine that performs D function (which calls itself):
> 
> void D() {
>  D();
> }
> 
> Easy?

The function has no arguments so we may require that the tape of the
Turing machine is initally empty. The the Turing machine needs only
one rule:

in the initial state, if the tape position under the head is empty,
leave the tape psition under the head empty and move forward and
continue in the initial state.

-- 
Mikko