Jail system is Turing-complete
Jump to navigation
Jump to search
Let's assume there are infinite people (there aren't really, but that doesn't matter), and there is one judge.
The judge can go from interviewing different people at a time, so >
and <
are down.
Since Brainfuck's system only needs two possible symbols per spot on tape to be Turing-complete, the jail system also has two symbols. Innocent and guilty.
(Everyone starts out innocent.)
Therefore, +
and -
are down as well.
The judge can use a "judgement process" depending on which people are innocent and which ones are guilty.
This means the brackets []
are also down.
Therefore, the jail system is Turing-complete. (The system, not in practice)