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:17:54 +0300
Organization: -
Lines: 39
Message-ID: <10044f2$30tug$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>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 15 May 2025 09:17:55 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="1d3ea60c43909c97d925f5b2a4bb28e2";
	logging-data="3176400"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+U9TBUM/9ZvmA0DZ+qsonf"
User-Agent: Unison/2.2
Cancel-Lock: sha1:OxaNkbYswX2/DltRQE4a3wFe54I=
Bytes: 2968

On 2025-05-14 20:00:13 +0000, Keith Thompson said:

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

Post found that Turing's original machine could be simplified so that
every computation possible with the original machie is possible with
the simplified machine but reasoning about the simpified macnies is
simpler and easier than about the original machines. One of the
simplifications is that the tape has no beginning.

-- 
Mikko