Wednesday, August 29, 2007

Mr Turing, meet Endo

From the moment we saw what Endo's DNA was doing as we ran it, every ICFP contestant (at least, those who got that far) knew in their hearts that Fuun DNA is Turing complete. But I am a mathematician! And mathematicians need proof.

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.

Sunday, August 26, 2007

On an open problem of Wolfram

I have something to admit. Something rather shameful. I never learnt Fuun during the contest. After all, I was a late arrival to a team with a man we call Bruce Almighty, after whom the Bruce-First Search is named. Although I had a vague understanding of the low-level details, my contributions were mostly at a higher level.

So I'm only really learning the details now, as I don my tin-foil hat and prepare for a Fuun-filled future. When I saw Jochen's ingenious 55-character junk generator, I had only an inkling of how it worked until I whipped out my spec booklet and a pencil. Jochen's string shows just how incredibly rich Fuun DNA is. And also that Jochen is a brilliant DNA hacker.

I will now, finally, progress to my point. Last week, I left you with an SHA-1 "essence" of a result. In truth, it is more of a question than a result. It is suspected by some that the following DNA sequence has a truly awe-inspiring property: that the genetic program of any being can be emulated by this sequence of Fuun genes. Is this the case? A cash prize is offered for a proof of the affirmative.

IIPIFFCFPPPIICIIPIFFCFPPFIICIIPIFFCFPPPIICIICIFPIC
PIFPCPIFPICPIICICFFFICFCIPFICFCCCCICFCPICFCFICFFII
CFFCIIPIFFCFPFCIICICPCFPFFFPCFPFICCFPFPCFPPCIICIFP
PICPCFPFFFFCFPFICCFPFPCFPPCFCCFPFICIICIIPIFFCFPFCI
ICICPCFPFFFPCFPFICCFPFPIIPIFFCFPFICIICIIPIFFCFPPCI
ICIICIFPPICPCFPFFIFPCPCFPFPIFPICPFCCFPFICIICIIPIFF
CFPFCIICICPCFPFFFCCFPFICCFPFPCFPPCIICIFPPICPCFPFFF
FCFPFICCFPFPCFPPCFPCFPFICIICIIPIFFCFPFCIICICPCFPFF
FCCFPFICCFPFPIIPIFFCFPFICIICIIPIFFCFPPCIICIICIFPPI
CPCFPFFIFPCPCFPFPIFPICPFPCFPFICIICIIPIFFCFPFCIICIC
PCFPFFFFCFPFICCFPFPIIPIFFCFPPCIICCFPPFIICIFPPICICC
FPFFFFCFPFICCFPFPFCCFPFICIFPCPCFPPFIICIIPIFFCFPFCI
ICICPCFPFFFFCFPFICCFPFPIIPIFFCFPPCIICIIPIFFCFPFICI
ICIICIFPPICICCFPFFIFPICPCFPFPFCCFPFICIFPCPIICIIPIF
FCFPFCIICICICCFPFFFPCFPFICCFPFPIIPIFFCFPPCIICCFPPF
IICIFPPICPCFPFFFFCFPFICCFPFPFFCFPFICIFPCPCFPPFIICI
IPIFFCFPFCIICICICCFPFFFPCFPFICCFPFPIIPIFFCFPPCIICI
IPIFFCFPFICIICIICIFPPICPCFPFFIFPICPCFPFPFFCFPFICIF
PCPIICIIPIFFCFPFCIICICICCFPFFFCCFPFICCFPFPIIPIFFCF
PPCIICCFPPFIICIFPPICICCFPFFFFCFPFICCFPFPFPCFPFICIF
PCPCFPPFIICIIPIFFCFPFCIICICICCFPFFFCCFPFICCFPFPIIP
IFFCFPPCIICIIPIFFCFPFICIICIICIFPPICICCFPFFIFPICPCF
PFPFPCFPFICIFPCPIICIIPIFFCFPFCIICICICCFPFFFFCFPFIC
CFPFPCFPPCIICIFPPICPCFPFFFFCFPFICCFPFPCFPPCFPCFPFI
CIICIIPIFFCFPFCIICICICCFPFFFFCFPFICCFPFPIIPIFFCFPF
ICIICIIPIFFCFPPCIICIICIFPPICPCFPFFIFPCPCFPFPIFPICP
FPCFPFICIICIIPIFFCFPPPIICIIPIFFCFPPFIICIIPIFFCFPPP
IICIICIFPICPIFPCPIFPICPIICICFFF

Thursday, August 23, 2007

Investigating Endo: Junk DNA

My friend Marco has blogged about my team's experience in the ICFP, but since the contest, I've been investigating Endo's DNA. Johann Jeuring is slowly revealing some interesting facts, but as we know, he was kidnapped by Fuun invaders, and so we can't really trust what he tells us.

I've discovered some truly remarkable properties of Fuun DNA, the proof of which this blog is wide enough to contain. Unfortunately Earth's internet has already been infiltrated by Fuun agents, as attested by their subversion of the ICFP itself.

I will, however, reveal a single DNA sequence, which may prove useful in the defense against Fuun invaders, should they further threaten our planet. When "executed" it generates large amounts of "junk DNA". JB and HM indicate that in generates on the order of 10865 acids in about 101730 iterations before destroying itself, but of course our gene simulators would take many years to confirm this.

Anyone who discovers more about this sequence or others related to it should post them on this blog, so that we may broaden our knowledge of our universe's lifeforms, and begin to coordinate anti-Fuun defense, should it be necessary.

IIPIFFCFPPPIICIIPIFFCFPPFIICIIPIFFCFPPPIICIICIFPIC
PIFPCPIFPICPIICICFFFICFCIPIICFCCCCICFCPICFCFICFFII
CFFCIIPIFFCFPFCIICICCCFPFFFFCFPFICCFPFPIIPIFFCFPPC
IICCFPPFIICIFPPICFCFPFFFFCFPFICCFPFPFCCFPFICIFPCPC
FPPFIICIIPIFFCFPFCIICICCCFPFFFFCFPFICCFPFPIIPIFFCF
PPCIICIIPIFFCFPFICIICIICIFPPICFCFPFFIFPICPCFPFPFCC
FPFICIFPCPIICIIPIFFCFPFCIICICCCFPFFFCCFPFICCFPFPCF
PPCIICIFPPPFCFPFFFFCFPFICCFPFPCFPPCFFCFPFICIICIIPI
FFCFPFCIICICCCFPFFFCCFPFICCFPFPIIPIFFCFPFICIICIIPI
FFCFPPCIICIICIFPPPFCFPFFIFPCPCFPFPIFPICPFFCFPFICII
CIIPIFFCFPFCIICICFCFPFFFFCFPFICCFPFPIIPIFFCFPPCIIC
CFPPFIICIFPPICPCFPFFFFCFPFICCFPFPFFCFPFICIFPCPCFPP
FIICIIPIFFCFPFCIICICFCFPFFFFCFPFICCFPFPIIPIFFCFPPC
IICIIPIFFCFPFICIICIICIFPPICPCFPFFIFPICPCFPFPFFCFPF
ICIFPCPIICIIPIFFCFPFCIICICFCFPFFFCCFPFICCFPFPIIPIF
FCFPPCIICCFPPFIICIFPPICICCFPFFFFCFPFICCFPFPFFCFPFI
CIFPCPCFPPFIICIIPIFFCFPFCIICICFCFPFFFCCFPFICCFPFPI
IPIFFCFPPCIICIIPIFFCFPFICIICIICIFPPICICCFPFFIFPICP
CFPFPFFCFPFICIFPCPIICIIPIFFCFPFCIICICPCFPFFFFCFPFI
CCFPFPCFPPCIICIFPPICICCFPFFFFCFPFICCFPFPCFPPCFCCFP
FICIICIIPIFFCFPFCIICICPCFPFFFFCFPFICCFPFPIIPIFFCFP
FICIICIIPIFFCFPPCIICIICIFPPICICCFPFFIFPCPCFPFPIFPI
CPFCCFPFICIICIIPIFFCFPFCIICICPCFPFFFCCFPFICCFPFPII
PIFFCFPPCIICCFPPFIICIFPPPCCFPFFFFCFPFICCFPFPFCCFPF
ICIFPCPCFPPFIICIIPIFFCFPFCIICICPCFPFFFCCFPFICCFPFP
IIPIFFCFPPCIICIIPIFFCFPFICIICIICIFPPPCCFPFFIFPICPC
FPFPFCCFPFICIFPCPIICIIPIFFCFPFCIICICICCFPFFFFCFPFI
CCFPFPCFPPCIICIFPPPCCFPFFFFCFPFICCFPFPCFPPCFFCFPFI
CIICIIPIFFCFPFCIICICICCFPFFFFCFPFICCFPFPIIPIFFCFPF
ICIICIIPIFFCFPPCIICIICIFPPPCCFPFFIFPCPCFPFPIFPICPF
FCFPFICIICIIPIFFCFPFCIICICICCFPFFFCCFPFICCFPFPCFPP
CIICIFPPICICCFPFFFFCFPFICCFPFPCFPPCFFCFPFICIICIIPI
FFCFPFCIICICICCFPFFFCCFPFICCFPFPIIPIFFCFPFICIICIIP
IFFCFPPCIICIICIFPPICICCFPFFIFPCPCFPFPIFPICPFFCFPFI
CIICIIPIFFCFPFCIICPCCFPFFFFCFPFICCFPFPIIPIFFCFPPCI
ICCFPPFIICIFPPICCCFPFFFFCFPFICCFPFPFFCFPFICIFPCPCF
PPFIICIIPIFFCFPFCIICPCCFPFFFFCFPFICCFPFPIIPIFFCFPP
CIICIIPIFFCFPFICIICIICIFPPICCCFPFFIFPICPCFPFPFFCFP
FICIFPCPIICIIPIFFCFPFCIICPCCFPFFFCCFPFICCFPFPIIPIF
FCFPPCIICCFPPFIICIFPPICPCFPFFFFCFPFICCFPFPFCCFPFIC
IFPCPCFPPFIICIIPIFFCFPFCIICPCCFPFFFCCFPFICCFPFPIIP
IFFCFPPCIICIIPIFFCFPFICIICIICIFPPICPCFPFFIFPICPCFP
FPFCCFPFICIFPCPIICIIPIFFCFPFCIICPFCFPFFFFCFPFICCFP
FPCFPPCIICIFPPICCCFPFFFFCFPFICCFPFPCFPPCFCCFPFICII
CIIPIFFCFPFCIICPFCFPFFFFCFPFICCFPFPIIPIFFCFPFICIIC
IIPIFFCFPPCIICIICIFPPICCCFPFFIFPCPCFPFPIFPICPFCCFP
FICIICIFFCFPFCPFCFPFFFCCFPFICIFFCFPPPIICIICIIPIFFC
FPPPIICIIPIFFCFPPFIICIIPIFFCFPPPIICIICIFPICPIFPCPI
FPICPIICICFFF


As a token, I leave you with this essence of my deepest result yet: 54c763a5f6b9beba26eeae2e98ba786f45b0fef8.

EDIT: Thanks to Jochen for the correction. In case you were worrying, he is not a Fuun agent: I have carefully checked his patch.