Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Keith Thompson <Keith.S.Thompson+u@gmail.com>
Newsgroups: comp.theory
Subject: Re: How to write a self-referencial TM?
Date: Wed, 14 May 2025 17:19:08 -0700
Organization: None to speak of
Lines: 25
Message-ID: <87zffe914z.fsf@nosuchdomain.example.com>
References: <1e4f1a15826e67e7faf7a3c2104d09e9dadc6f06.camel@gmail.com>
	<1002akp$2i4bk$2@dont-email.me>
	<479eebef3bd93e82c8fe363908b254b11d15a799.camel@gmail.com>
	<1002j0r$2k04b$1@dont-email.me>
	<3b177909de383fcf209cfb9ff81fe2f118640578.camel@gmail.com>
	<1002l44$2k04b$3@dont-email.me>
	<8c7a8437e78a5b798cc23d77a8e1b6080e59ab0e.camel@gmail.com>
	<1002nvo$2k04b$5@dont-email.me>
	<87plgb9d4i.fsf@nosuchdomain.example.com>
	<1002tma$2k04c$5@dont-email.me> <1003bbu$2d57f$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Thu, 15 May 2025 02:19:08 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="5a831048c3367e529229a64cc925cf0c";
	logging-data="2901297"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/nr+0mdWnSHAPVMyekM8EF"
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:V1eVV5Wsb29ZekByLBmsClRyacw=
	sha1:FcBFBwBOxlOn6YdUGchrtYlQXhA=

Andy Walker <anw@cuboid.co.uk> writes:
> On 14/05/2025 21:16, Richard Heathfield wrote:
>> On 14/05/2025 21:00, Keith Thompson wrote:
>>> I presume that one-way and two-way infinite tapes are computationally
>>> equivalent, so the distinction doesn't matter all that much.
>
> 	Indeed, there are lots of computationally equivalent versions:
>
>  -- two or more tapes [indeed, two-dimensional tapes]
>  -- one-way or two-way
>  -- "paper" tapes where you can punch holes to change the content but not
>       stick the chad back in to "unpunch" the holes
>  -- two symbol, three symbol, ...
>  -- move two or more spaces at a time
>  -- others I've forgotten

Not to mention the very common variant where landing on Free Parking
means you get all the money from the center of the board.  Or was that
something else?

[...]

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */