All quines in existence can be presented by this lambda expression:
The Turing Machine equivalent to this is given one symbol @, the rewrite rule:
(Where O is an empty space now)
And the Turing Machine head moving forward one symbol cell.
These are very closely interconnected.
Lambda application is equivalent to executing a Turing Machine "tick".
Finding the symbols to be substituted is equivalent to the Turing Machine head moving leftward on the tape.
The actual substitution itself is equivalent to the Turing Machine head writing the new symbol.
Anything capable of recursion or iteration can represent a quine.
Most programming languages use the lambda calculus example, because compilers are the ones reading the generated source code. This means lambda application is not just running, but also compiling the code to be run. This explains why almost all examples exhibit nearly the exact same pattern (https://en.wikipedia.org/wiki/Quine_(computing)). The pattern being having the "work" program code around the code to be duplicated.
The smallest possible quine based on this is: %. A function that takes an input and prints itself and the input again. I declare this quinelang. Some examples, where anything to the right of % is passed to the function.
(λx.x x)(λx.x x)
...or my favorite: λ1 1λ1 1
@ -> O@
(Where O is an empty space now)
And the Turing Machine head moving forward one symbol cell.
These are very closely interconnected.
Lambda application is equivalent to executing a Turing Machine "tick".
Finding the symbols to be substituted is equivalent to the Turing Machine head moving leftward on the tape.
The actual substitution itself is equivalent to the Turing Machine head writing the new symbol.
Anything capable of recursion or iteration can represent a quine.
Most programming languages use the lambda calculus example, because compilers are the ones reading the generated source code. This means lambda application is not just running, but also compiling the code to be run. This explains why almost all examples exhibit nearly the exact same pattern (https://en.wikipedia.org/wiki/Quine_(computing)). The pattern being having the "work" program code around the code to be duplicated.
The smallest possible quine based on this is: %. A function that takes an input and prints itself and the input again. I declare this quinelang. Some examples, where anything to the right of % is passed to the function.
%s = %s
%hello this is a test = %hello this is a test
%% = %%
But that is for a quine defined as needing to output source for a compiler and a valid program has at least one function and application of that function. For a single symbol quine we can use &. It takes no input and returns itself, which itself can be run and do the same again and again. This is exactly what the TI-BASIC example employs.
Comments
Post a Comment