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 21:19:04 +0100
Organization: Fix this later
Lines: 56
Message-ID: <1002tro$2k04c$7@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>
 <1002sth$2lvq0$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 14 May 2025 22:19:04 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="0c399434be0097fc2343dbe56cfc06f0";
	logging-data="2752652"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18TB8tPaAXNpY0lSMFiDQnSRNyOMmkLOB4Q0J59yxPaGQ=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:3WS1UIO/nXlLAkOwTugEyofD5hk=
In-Reply-To: <1002sth$2lvq0$2@dont-email.me>
Content-Language: en-GB

On 14/05/2025 21:02, olcott wrote:
> On 5/14/2025 3:00 PM, Keith Thompson wrote:
>> Richard Heathfield <rjh@cpax.org.uk> writes:
>> [...]
>>> See <https://plato.stanford.edu/entries/turing-machine/>
>>>
>>> where you can read this:
>>>
>>> "A Turing machine then, or a computing machine as Turing 
>>> called it, in
>>> Turing’s original definition is a machine capable of a finite 
>>> set of
>>> configurations q1,…,qn (the states of the machine, called
>>> m-configurations by Turing). It is supplied with a one-way 
>>> infinite
>>> and one-dimensional tape divided into squares each capable of 
>>> carrying
>>> exactly one symbol. At any moment, the machine is scanning the 
>>> content
>>> of one square r which is either blank (symbolized by S0) or 
>>> contains a
>>> symbol S1,…,Sm with S1=0 and S2=1."
>>>
>>> There's more to TMs than tapes.
>> [...]
>>
>> Interesting.  The phrase "one-way infinite" implies that the tape
>> is infinite in only one direction, so the cells can be indexed by
>> non-negative integers.  Elsewhere on that web page, it 
>> acknowledges
>> that there are variations in Turing machines, including one-way
>> vs. two-way infinite tapes.  It's implied that Turings original
>> concept had a one-way infinite tape.  I wasn't able to confirm or
>> deny that in a very quick look through Turings original paper.
>>
>> I've always assumed that a TM tape is two-way infinite.
>>
>> 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 don't think that is precisely accurate.
> A unlimited tape is not an infinite tape
> it merely has all of the space that it needs.

Correct.

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