- tags
- Turing-completeness
- source
- Gwern Branwen’s website
Turing-completeness is common
TC [Turing-completeness], […] is […] weirdly common: one might think that such universality as a system being smart enough to be able to run any program might be difficult or hard to achieve, but it turns out to be the opposite and it is difficult to write a useful system which does not immediately tip over into TC.
I’ve often been amazed at how common TC can be in sufficiently complicated systems. Because it is so common, Gwern decides to distinguish Accidentally Turing complete systems from Surprisingly Turing complete ones.
Accidentally Turing complete systems aren’t very interesting. They’re usually the result of too much complexity built into a game / standard / system / etc.
Surprisingly Turing-complete
The other list is made of systems where one of the primitive is powerful enough to make the whole thing Turing complete. They are really not supposed to be TC; naturally, they are very inefficient, often achieving TC via implementation of a CA construction.
Implications for computer security
Beyond the interest these unexpectedly TC systems represent, security implications can be problematic.
Why this effort to make a language in which many programs can’t be written? Because TC is intimately tied to Gödel’s incompleteness theorem & Rice’s theorem, allowing TC means that one is forfeiting all sorts of provability properties: in a non-TC language, one may be able to easily prove all sorts of useful things to know; for example, that programs terminate, that they are type-safe or not, that they can be easily converted into a logical theorem, that they consume a bounded amount of resources, that one implementation of a protocol is correct or equivalent to another implementation, that there are a lack of side-effects and a program can be transformed into a logically-equivalent but faster version