Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Andy Walker Newsgroups: comp.theory Subject: Re: How to write a self-referencial TM? Date: Thu, 15 May 2025 01:09:34 +0100 Organization: Not very much Lines: 71 Message-ID: <1003bbu$2d57f$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> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Thu, 15 May 2025 02:09:34 +0200 (CEST) Injection-Info: dont-email.me; posting-host="4261c6f647bd9b5d86ddef2e007b2a75"; logging-data="2528495"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+pPGo1H5L6bGLg7hQ4UpZA" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:qwsADlIxBgFN65zeXRopD4l+EOg= Content-Language: en-GB In-Reply-To: <1002tma$2k04c$5@dont-email.me> On 14/05/2025 21:16, Richard Heathfield wrote: > On 14/05/2025 21:00, Keith Thompson wrote: >> I presume that one-way and two-way infinite tapes are computationally >> equivalent, so the distinction doesn't matter all that much. Indeed, there are lots of computationally equivalent versions: -- two or more tapes [indeed, two-dimensional tapes] -- one-way or two-way -- "paper" tapes where you can punch holes to change the content but not stick the chad back in to "unpunch" the holes -- two symbol, three symbol, ... -- move two or more spaces at a time -- others I've forgotten Once you've shown they're equivalent, you can use a convenient version to solve problems and the simplest versions to investigate theoretical limits. See below for more info. >> (Though with a one-way tape, I'm not sure what happens if the TM >> runs off the end of the tape.) It's helpful to have an end-of-tape "marker" [could be a symbol used only for this purpose]. > I should imagine that you could build one hell of a stack on one-way tape. Yes, but for theoretical purposes you probably need two stacks [or near equivalents] to hold two arbitrary-length integers. On the other hand, the tape can be read as two integers reading outwards from the head position, and the TM transitions then correspond to fiddling with the least-significant digits of these integers. See also below. > 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. An alternative view is that you can attach a "tape factory" to your TM, and add a new square or three when you would otherwise run off the end. > 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. When I was lecturing this stuff, it was common for software to be delivered as a stack of floppy discs accompanied by instructions such as "now mount the next disc". So I used to point out to the students that this was quite precisely a TM. The PC was a FSM which could read/write "squares" consisting of one floppy disc each containing several million binary digits depending on the state of the PC, from time to time going to the next or previous floppy. If you didn't have a next floppy, you went to a shop and bought some more. All the material described above is discussed in my lecture notes, on the Web starting at https://www.cuboid.me.uk/anw/G12FCO/header.html [see especially the last few lectures/problem classes/courseworks, all linked from the header page]. Of course, there are many other excellent web pages and books that discuss this stuff with varying degrees of formality and level of maths/logic required as a pre-requisite. [May be worth noting that the references to emulation and to self- referential programs in lecture 18 pre-date musings by Messrs Olcott and Flibble by years, and they certainly weren't original to me.] -- Andy Walker, Nottingham. Andy's music pages: www.cuboid.me.uk/andy/Music Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Heller