8
W jaki sposób argumentujesz, że rachunek lambda jest ukończony przez Turinga (w najprostszy możliwy sposób)?Turing kompletność rachunku lambda?
A
Odpowiedz
8
Najprostszym sposobem jest wdrożenie maszyny Turinga w rachunku Lambda. Jest to dość łatwe, ponieważ rachunek Lambda jest praktycznie językiem programowania wysokiego poziomu. Takie podejście ma tę zaletę, że nie wymaga żadnych innych zależności matematycznych, a zatem powinno zapewnić możliwie najprostszy sposób dostarczenia argumentów.
Pod względem dowodu matematycznego najkrótszą drogą jest zastosowanie innego paradygmatu, który już został wykazany jako Turing complete, podobnie jak funkcje μ-recursive. Są one już rekursywnie zdefiniowane, więc ich ekspresja w rachunku lambda jest nieco bardziej elegancka niż sama maszyna Turinga.
1
brainfuck jest językiem, który bardzo dokładnie modele Maszyna Turinga, i może się okazać, nakreślono w http://en.wikipedia.org/wiki/Binary_lambda_calculus#Brainfuck
interpreter rachunek lambda wykazać, że wszystkie [funkcje ľ-rekurencyjne] (https: //en.wikipedia .org/wiki /% CE% 9C-recursive_function) mogą być wyrażone w rachunku lambda, a następnie polegać na wyniku Turinga-zupełności dla tych –