Полнота лямбда-исчисления по Тьюрингу?
Как вы аргументируете тот факт, что лямбда-исчисление является полным по Тьюрингу (самым простым из возможных способов) ?
2 ответа:
Наиболее простым способом является реализация машины Тьюринга в лямбда-исчислении. Это довольно легко, потому что лямбда-исчисление-это практически язык программирования высокого уровня. Этот подход имеет то преимущество, что не требует каких-либо других математических зависимостей, и поэтому он должен обеспечить простейший возможный способ представления аргумента.
В терминах математического доказательства кратчайший путь лежит через реализацию другой парадигмы, которая уже была показана как Тьюринг полные, как и µ-рекурсивные функции. Они уже рекурсивно определены, поэтому их выражение в лямбда-исчислении несколько элегантнее, чем сама машина Тьюринга.
Brainfuck-это язык, который очень точно моделирует машины Тьюринга, и вы можете найти интерпретатор лямбда-исчисления, прописанный на http://en.wikipedia.org/wiki/Binary_lambda_calculus#Brainfuck