Path: ...!eternal-september.org!feeder3.eternal-september.org!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:24:34 +0300
Organization: -
Lines: 50
Message-ID: <10044ri$3108g$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> <PH7VP.224787$JJT6.10824@fx16.ams4>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 15 May 2025 09:24:35 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="1d3ea60c43909c97d925f5b2a4bb28e2";
	logging-data="3178768"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+d1sPn0rG0Ddo/I2chN+B1"
User-Agent: Unison/2.2
Cancel-Lock: sha1:1nKIOIUd17hBSVK4M3UXqEQzHa4=
Bytes: 3351

On 2025-05-14 21:13:19 +0000, Mr Flibble said:

> On Wed, 14 May 2025 13:49:03 -0700, Keith Thompson wrote:
> 
>> Richard Heathfield <rjh@cpax.org.uk> writes:
>>> On 14/05/2025 21:00, Keith Thompson wrote:
>>> <snip>
>>> 
>>>> I presume that one-way and two-way infinite tapes are computationally
>>>> equivalent, so the distinction doesn't matter all that much.
>>>> (Though with a one-way tape, I'm not sure what happens if the TM runs
>>>> off the end of the tape.)
>>> 
>>> I should imagine that you could build one hell of a stack on one-way
>>> tape.
>>> 
>>> Of course, the tape doesn't /have/ to be infinite. It only has to be
>>> long enough so that you /don't/ run off the end. Just how long that is
>>> depends on what problem you're addressing.
>>> 
>>> 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.
>> 
>>> 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".  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.
> 
> Flibble's Law still applies:
> 
> If a problem permits infinite behavior in its formulation, it permits
> infinite analysis of that behavior in its decidability scope.

You cannot pose in finite time a problem that has an infinite behaviour
in its formulation. If the problem will not be posed in a finite time
it will never be solved.

-- 
Mikko