Turing complete Blitter/Copper

[Mrs Beanbag]

Following on from something somebody over on EAB said the other day...

The suggestion is, if the Copper can control the Blitter, and you can blit into a copper list, could one make it Turing complete?

Well the simple answer is yes, because it occurred to me that one could perform a finite number of steps of Rule 110 using the Blitter without any intervention at all. The Copper could be used to make it carry on indefinitely.

But perhaps Rule 110 isn't the ideal cellular automaton for this kind of application. Any alternative ideas? And what could you use it for?

[Mrs Beanbag]

do you know Rule 110?
Set blitter sources A, B, C to point to the same address.
blitter source A shift right 1 (or rather, 15px left with a 2 byte offset on its pointer)
source B shift left 1
copy to the next line using the correct Minterms to generate the Rule 110  truth table.
and that's it. If the destination line is immediately above/below the source line one could blit a whole block and it would just work.

[Mrs Beanbag]

Well it turns out Rule 110 is equivalent to a sort of regular expressions engine, would be very interesting to see if a regular regular expression could be converted into the required bitstream. Regular expressions with the Blitter, hmm...

There's another way to do Rule 110 with the Blitter, if you do it sideways you could do 16 Rule 110's in parallel.

[Mrs Beanbag]

Well it generates pretty pictures! But more importantly it's a proof (of Blitter Turing completeness). Other more convenient cellular automata might be possible. If you can do Rule 110 you can, in theory, do anything at all.