Wikipedia:Reference desk/Archives/Mathematics/2020 November 12
| Mathematics desk | ||
|---|---|---|
| < November 11 | << Oct | November | Dec >> | Current desk > |
| Welcome to the Wikipedia Mathematics Reference Desk Archives |
|---|
| The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
November 12
editTuring machine numbers and their rules table
editIn the literature, I've seen Turing Machines referred to by their number. How do you translate between their number and their rules table? (I've searched and can't find it.) Bubba73 You talkin' to me? 17:24, 12 November 2020 (UTC)
- The point is that there are only countably many Turing machines, and they can be enumerated in a way that allows translating their behavior into statements of arithmetic. Pretty much any way of enumerating them that you try is likely to work; the details aren't really that important. See Goedel number. --Trovatore (talk) 20:56, 12 November 2020 (UTC)
- I do not know if there is a universally agreed translation, but if the numbers consist of only the digits "1" through "7", where the "7"s are followed by a "3" (unless final), and a "3" tends to be followed by a sequence of "1"s, as in "31332531173113353111731113322531111731111335317", then it is almost surely Turing's original recipe given in his 1936 paper "On Computable Numbers". It is given in the original publication in the Proceedings of the London Mathematical Society on page 240 halfway through Section 5, "Enumeration of computable sequences". In the reprint in Davis' The Undecidable this is on page 126. To find the spot in other editions, scan for "description number". --Lambiam 21:10, 12 November 2020 (UTC)
- In particular, I was wondering about the machine numbers here and how to convert between the number to the rule. Bubba73 You talkin' to me? 21:55, 12 November 2020 (UTC)
- It seems to be the enumeration counter in the class TM(5) of the enumeration program bbfind, linked to from the Busy Beaver prover page of Skelet (Georgi Georgiev). The programmer did not make it easy to understand the relationship with the TM table by using a global variable named m for that counter, while using the same name for many instances of procedure parameters and local variables. --Lambiam 23:14, 12 November 2020 (UTC)
- In particular, I was wondering about the machine numbers here and how to convert between the number to the rule. Bubba73 You talkin' to me? 21:55, 12 November 2020 (UTC)
Resolved