Open rdebath opened 9 years ago
Hi! I was reading about it today but could not find any enough documentation on it.
I saw the loop limitation and I'll work on fixing it soon. Is there something more to make it TC? Where can I read more about it?
Thanks!
Wikipedia seems to have a pretty much complete description of Turing completeness but it's a good thing this isn't a paper encyclopaedia where you can't open a dozen tabs at once! Usually when there's this much jargon the simple English version can help but in this case that particular page is a bit stubby. The Turing machine page looks better, it even has a picture of a physical (finite) Turing machine emulation but it does still feel a bit short.
Brainfuck (and Ρ″ ) are Turing machine variants, though it's not immediately obvious that they are complicated enough, so a mathematical proof had to be done to confirm that they are in fact equivalent to proper Turing machines.
So to "prove" that your machine is Turing complete the simplest is usually to design a direct translation of any program from a known TC language (eg: BF) to your language. The loops are a normal implementation problem so they are not important for the proof; the only other item is that you've specifically limited the number of cells on the tape (it isn't a "push down" stack BTW). While everyone knows that an infinite machine is impossible they see it as NOT TC if you just write down a number rather than saying something like "limited by the implementation to 64k cells". After that infinite storage is just a minor implementation detail. :grinning:
Thanks for your reply! Cool video btw
As I have to split time into university and work, for now I will fix the 64k limit and the loop issues. Then I will study it deep, so I plan to make Cood TC asap!
This language is a Ρ″ clone (also known as a brainfuck derivative), however, it is not currently Turing complete (or BSM) because the loop construct in your implementation is not sufficiently versatile.
For Turing completeness the loops must be nestable and skip able. So, for example, the below would print out a "Hello World!" message.