Am einfachsten ist es, eine Turing-Maschine in den Lambda-Kalkül einzubauen. Das ist ziemlich einfach, weil der Lambda-Kalkül praktisch eine höhere Programmiersprache ist. Dieser Ansatz hat den Vorteil, dass keine anderen mathematischen Abhängigkeiten erforderlich sind, und er sollte daher die einfachste Möglichkeit bieten, Ihr Argument zu liefern.
Im Sinne eines mathematischen Beweises geht der kürzeste Weg dahin, indem ein anderes Paradigma implementiert wird, von dem bereits gezeigt wurde, dass es vollständig Turing ist, wie μ-rekursive Funktionen. Diese sind bereits rekursiv definiert, so dass ihr Ausdruck im Lambda-Kalkül etwas eleganter ist als die Turing-Maschine selbst.
Brainfuck ist eine Sprache, die Turing Machines sehr genau beschreibt, und Sie können einen Lambda-Kalkül-Interpreter finden Ссылка
Tags und Links theory turing-machines turing-complete computability