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 14:40:30 -0700
Organization: None to speak of
Lines: 30
Message-ID: <87cycaan1t.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>
	<87ldqyapfk.fsf@nosuchdomain.example.com>
	<10031uo$2n1is$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Wed, 14 May 2025 23:40:31 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="28f21fc31a5e376fbb703380c9354ddd";
	logging-data="2799377"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19cECRsgfBaG4eyUPr8t6yt"
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:UdoCX79pA7Ig8Ibie/4s5rs3BKo=
	sha1:swuqP+Eslmm8urjjlwqHc4ZjCU0=

Richard Heathfield <rjh@cpax.org.uk> writes:
[...]
> Using a highly questionable collection of approximations about the
> physical properties of 4mm mylar tape and the number of atoms in the
> universe, I calculated that by devoting /everything/ to this tape we
> could make it
>
> 5285412262156448202959830866807610993657505285
>
> lightyears long (exACtly, of course).
>
> It's still a long way off infinite, but I think it could possibly
> qualify as 'long enough'.

It's still not long enough for a TM that repeatedly advances its
position in one direction while indefinitely repeating the same state.

In C terms, there is no real world output device that can hold the
output of `while (1) putchar('x');`.

It's the unboundedness of the tape that makes the halting problem
unsolvable.  It's what allows the combined internal (finite state)
and external (unbounded tape) state of a TM to be unbounded.  If we
considered only TMs that consume less than N tape cells, for any
finite N, the halting problem *for such TMs* would be theoretically
solvable by detecting or not detecting a repeated state.

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