Turing Completer
- This is still a work in progress. It may be changed in the future.
Turing Completer is a theoretical language capable of generating a Turing Completeness Proof for any language. There are 2 variations for this language, one which could theoretically be implemented (Potential Completer) and one which is impossible to implement (Omnipotent Completer). It was created by user:Bertrahm.
General Overview
Both forms of the Turing Completer only have one instruction which is
Generate Proof For <Language Name>
In the case of the Potential Completer, it would have to be provided information about the language via a Program Argument containing the path to a file containing the languages information.
Potential Completer
The Potential Completer would only be able to generate a Turing Completeness Proof for languages in which it is actually possible. For this it would require a set of the language's instructions, their behaviour and syntax along other rules. Implementing this would theoretically be possible, although it would be hard.
Omnipotent Completer
The Omnipotent Completer would be impossible to implement for 2 main reasons:
- It would only require a language's commonly adapted name to generate a Turing Completeness Proof
- It would be able to create proof that would always work for languages where it would be impossible like Anarchysm.
The second point makes the Omnipotent Completer paradoxical, since it would be able to generate proof that would always work for a language like Anarchysm, where the language "does what it wants".
Computational Class
Perhaps surprisingly, Turing Completer is itself Turing Complete. Simply consider the class of languages defined like "Brainfuck except [ first computes <some Turing Machine> and skips the loop unless it halts in an accepting state".