Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.theory
Subject: Re: How to write a self-referencial TM?
Date: Wed, 14 May 2025 22:28:54 +0100
Organization: Fix this later
Lines: 53
Message-ID: <10031uo$2n1is$1@dont-email.me>
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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 14 May 2025 23:28:57 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="0c399434be0097fc2343dbe56cfc06f0";
	logging-data="2852444"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+qwUoH4U8/CyoD4NvZzt1xCJOqHLnGLDRQR1f/F11sYw=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:XPVXc3KynmkyBcJlVgPrZHOrmRE=
In-Reply-To: <87ldqyapfk.fsf@nosuchdomain.example.com>
Content-Language: en-GB

On 14/05/2025 21:49, Keith Thompson wrote:
> Richard Heathfield <rjh@cpax.org.uk> writes:

<snip>

>>
>> In the Real World, tapes can't be infinite, so an implementor has to
>> decide how long 'long enough' is.
> 
> TM's don't necessarily operate in the Real World.

Of course. HP is a thought experiment, not an exercise for 
hardware engineers (or indeed software engineers). I just can't 
help turning my thoughts in that direction.

> 
>> If the TM's alphabet consisted of 256 discrete symbols (no reason why
>> not) a megabyte would give you a disk-based 'tape' a million cells
>> long.
>>
>> Ought to be enough for `take one down and pass it around'.
> 
> Sure.  "Infinite tape" might be more precisely expressed as
> "sufficient tape".

Quite so.

>  But a TM that advances in one direction along
> the tape in a loop will require more than any finite length of tape
> if you leave it running long enough, though the amount of tape it
> consumes in any finite number of steps is still finite.  For that
> kind of TM in particular, "infinite tape" is a convenient shorthand.

All acknowledged, all agreed.

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'.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within