Mr Turing, I'd like you to meet Endo:
IIPIFFPCPPPIICIIPIFFPCPPFIICIIPIFFPCPPPIICIICIFPIC
PIFPCPIFPICPIICFIFFFFIFCIPPFIFCCCIFIFCPFIFCFFIFIFC
PCIFIFCPFIFFIFIFFCIIPIFFPCPFCIICICICPCPFFPCPCPFICP
CPFPPCPPCIICIFPPICPPCPFFFFPCPFICPCPFPPCPPCFICPCPFI
CIICIIPIFFPCPFCIICICICPCPFFPCPCPFICPCPFPIIPIFFPCPF
ICIICIIPIFFPCPPCIICIICIFPPICPPCPFFIFPCPPCPFPIFPICP
FICPCPFICIICIIPIFFPCPFCIICICICPCPFFFICPCPFICPCPFPI
IPIFFPCPPCIICPCPPFIICIFPPICPPCPFFFCPCPFICPCPFPPCPC
PFICIFPCPPCPPFIICIIPIFFPCPFCIICICICPCPFFFICPCPFICP
CPFPIIPIFFPCPPCIICIIPIFFPCPFICIICIICIFPPICPPCPFFIF
PICPPCPFPPCPCPFICIFPCPIICIIPIFFPCPFCIICICICPCPFFFP
PCPFICPCPFPIIPIFFPCPPCIICPCPPFIICIFPPICICPCPFFFCPC
PFICPCPFPFCPCPFICIFPCPPCPPFIICIIPIFFPCPFCIICICICPC
PFFFPPCPFICPCPFPIIPIFFPCPPCIICIIPIFFPCPFICIICIICIF
PPICICPCPFFIFPICPPCPFPFCPCPFICIFPCPIICIIPIFFPCPFCI
ICICICPCPFFFFPCPFICPCPFPIIPIFFPCPPCIICPCPPFIICIFPP
ICICPCPFFFCPCPFICPCPFPFCPCPFICIFPCPPCPPFIICIIPIFFP
CPFCIICICICPCPFFFFPCPFICPCPFPIIPIFFPCPPCIICIIPIFFP
CPFICIICIICIFPPICICPCPFFIFPICPPCPFPFCPCPFICIFPCPII
CIIPIFFPCPFCIICICICPCPFFFCPCPFICPCPFPPCPPCIICIFPPI
CICPCPFFFFPCPFICPCPFPPCPPCFFPCPFICIICIIPIFFPCPFCII
CICICPCPFFFCPCPFICPCPFPIIPIFFPCPFICIICIIPIFFPCPPCI
ICIICIFPPICICPCPFFIFPCPPCPFPIFPICPFFPCPFICIICIIPIF
FPCPFCIICICPPCPFFPCPCPFICPCPFPPCPPCIICIFPPICPPCPFF
FFPCPFICPCPFPPCPPCFPPCPFICIICIIPIFFPCPFCIICICPPCPF
FPCPCPFICPCPFPIIPIFFPCPFICIICIIPIFFPCPPCIICIICIFPP
ICPPCPFFIFPCPPCPFPIFPICPFPPCPFICIICIIPIFFPCPFCIICI
CPPCPFFFICPCPFICPCPFPIIPIFFPCPPCIICPCPPFIICIFPPICP
PCPFFFCPCPFICPCPFPPCPCPFICIFPCPPCPPFIICIIPIFFPCPFC
IICICPPCPFFFICPCPFICPCPFPIIPIFFPCPPCIICIIPIFFPCPFI
CIICIICIFPPICPPCPFFIFPICPPCPFPPCPCPFICIFPCPIICIIPI
FFPCPFCIICICPPCPFFFPPCPFICPCPFPIIPIFFPCPPCIICPCPPF
IICIFPPICICPCPFFFCPCPFICPCPFPPCPCPFICIFPCPPCPPFIIC
IIPIFFPCPFCIICICPPCPFFFPPCPFICPCPFPIIPIFFPCPPCIICI
IPIFFPCPFICIICIICIFPPICICPCPFFIFPICPPCPFPPCPCPFICI
FPCPIICIIPIFFPCPFCIICICPPCPFFFFPCPFICPCPFPIIPIFFPC
PPCIICPCPPFIICIFPPICICPCPFFFCPCPFICPCPFPFCPCPFICIF
PCPPCPPFIICIIPIFFPCPFCIICICPPCPFFFFPCPFICPCPFPIIPI
FFPCPPCIICIIPIFFPCPFICIICIICIFPPICICPCPFFIFPICPPCP
FPFCPCPFICIFPCPIICIIPIFFPCPFCIICICPPCPFFFCPCPFICPC
PFPPCPPCIICIFPPICICPCPFFFFPCPFICPCPFPPCPPCFICPCPFI
CIICIIPIFFPCPFCIICICPPCPFFFCPCPFICPCPFPIIPIFFPCPFI
CIICIIPIFFPCPPCIICIICIFPPICICPCPFFIFPCPPCPFPIFPICP
FICPCPFICIICIIPIFFPCPPPIICIIPIFFPCPPFIICIIPIFFPCPP
PIICIICIFPICPIFPCPIFPICPIICFIFFF
I'm sure my (three, I think) regular readers have long ago worked out what I had up my sleeve, but this is it. Credit is due more to Cook and Wolfram than myself, and of course Endo and Turing, most of all.
I realise that Jeuring, et al. have probably had a proof of this fact for several months, but I believe I am the first to make it public.
To see this in action, configure your "build" program to output the current DNA at each iteration. The actual Turing machine data looks like this (it is surrounded front and back by the mechanics of the maching):
"PPPCI $State PPPCC $Symbol PPPCP PPPCF $LeftStack PPPFI $RightStack PPPFC"
$State is either "PP" (up) or "PF" (down). $Symbol is the symbol currently "under the head"; the symbols are "CI", "CC", "CF", "CP" and "FI", from white to black (note that I read NKS online, so I don't know what the colours are in the original). $LeftStack and $RightStack are lists of symbols delimited by "PPPCP", both starting with the tape cell nearest the head.
My previous Turing machines had a similar structure, but used "markers" other than "PPPxx".
EDIT: I have changed "FIFxx" for the markers, since strings of P's behave particularly badly in the face of quoting.
I'll leave the rest to you to work out.
Now... can we write a compiler before the organisers release theirs? I'm in the middle of a whole bunch of projects and tests, as well as practising for ACM ICPC, but I'd love to contribute if somebody else is prepared to lead for a bit.
Okay - lets see if I can get another chocolate fish...
ReplyDeleteI reopened my copy of NKS last night (for the first time in some months) to read some of the pages referred to in the online info about the 2,3 Turing machine prize. Oddly enough I found my bookmark was already sitting at page 709. Obviously I was already dreaming of the $25000 a few months ago! And about ten minutes before I saw your latest post I got my little Python emulation of the 2, 3 machine running... so with any luck the money should be mine by day's end!
Back to the chocolate fish - my guess is that this time you've presented us a Fuun DNA implementation of the 2, 5 Turing machine instead. I suppose I should download it now and give it a whirl...
A fuuny thing though, if you squint a little, and scroll up and down through your DNA listing above, you can also see faint echoes of larger patterns emerging from the apparent chaos... :)
Clive,
ReplyDeleteHmm... well, you can get the chocolate fish if you can tell me something interesting about the (2,3) machine. But I didn't really mean this as a puzzle: I even gave the number of symbols and states.
Oh, one thing I will give you a virtual chocolate for: what colours does Wolfram give the states of his machine? Tiring of white, grey1, grey2, grey3, grey4, I gave them my own colours, but I'd like to know the "official" colours, too.
If I do happen to find anything interesting about the 2, 3 machine I will consider sharing it with you... but of course I'll have to weigh up the relative values of a chocolate fish, the possibility of a $25000 prize, and that of whatever interesting info I find first!
ReplyDeleteWould you believe it, I skimmed your post so quickly the first time (before racing to write the first comment) that I didn't even spot the states and colours were given! I did see them later though on a more careful reading. So, yes, I see it really wasn't that hard to "guess". I retract my claim for the fish. :-)
As for the colours in the book, page 707 seems to be the one, and in my "first edition, third printing" it is also just shown as shades of grey. In fact, thumbing through it, there don't appear to be any coloured images in the body of the book at all.
Just another thought - wouldn't it have been easier to emulate a Cyclic Tag System instead? That would seem to map onto Fuun DNA almost directly (although, as per usual, I haven't tested this idea carefully!)
ReplyDeleteYes, it would certainly have been easier to do a cyclic tag system. So why didn't I? I could say that it's because Turing machines are better researched, more interesting, closer to the intuitive notion of computation.
ReplyDeleteBut the real answer is probably this: until your comment, I didn't know anything about cyclic tag systems (I haven't actually read NKS: I just copied the UTM's transition table from it). In fact, the only models of computation I had anything more than the vaguest idea about were TMs and the lambda calculus. TMs looked easier to implement, and I suspected the contest organisers already had a lambda calculus implementation. I wanted to do something that hadn't been done.