Turing Completeness and CAs
- Emma Byrne and I should that a big enough net of CAs is Turing complete.
- That's not too surprising as a net of continuous valued neurons
is super Turing complete (Siegelmann 91).
- We did it with CAs and no binding.
- If you add binding, you get rules, and you get Turing completeness
another way.
- So the question now becomes not can you program a brain, but how
does the brain program it.
- It's pretty clear that people use at least context free rules.
- So, to parse (or understand) natural language, you need to
use CF rules.
- You need binding (or a finite set of sentences) to use CF rules.