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?

[bloodline]

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?

You are going to need to post a proof, as I can't quite see it :-/

[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.

[polyp2000]

This sounds interesting - but is there any practical use for it?

N

[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.

[bloodline]

I wasn't aware of Rule 110, but having read up on it now, it is very involved... I doubt any Amiga would have enough Chip Ram to perform even a simple calculation!

[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.

[bloodline]

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.

With enough Chip Ram... :lol:

[polyp2000]

Id like to see this implemented - for sure!  Its been too long since i did any kind of real hacking on the amiga though.

[nicholas]

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.

yald?

[Blizz1220]

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.

So you're saying that Amiga's could in theory be evolved to self-thinking entities by using custom chips as their "brains"

http://www.youtube.com/watch?v=3zhqCccFsGc

[kamelito]

Are the 48MB of the FPGA Arcade enough ?   Kamelito