Представьте себе, лямбда-исчисление не зря называется "исчисление". Лямбда-исчисление задаёт такую же систему, как, например, язык Python и его интерпретатор. Представьте себе, любую программу на Python, которая вычисляет натуральное f(x) по x, можно записать в виде лямбда-выражения! Это и есть "программный код" в современном смысле. С помощью правила бета-редукции вы уже "исполняете" этот самый программный код.
Для вас же сейчас очевидно, что МТ - это совсем понятное описание компьютера, а лямбда-исчисление, как вам кажется, "просто способ записи функций". Но это не так. Это альтернативы описания одного и того же. В современном понимании - "программ" и их "исполнителей".
Что тут непонятного?!
В том и дело, что Чёрч, Тьюринг и другие рассуждали о вычислениях ещё до появления компьютеров, то есть, "автоматических вычислителей". Они пытались формализовать концепцию того, что, грубо говоря, можно вычислить на бумаге за конечное число шагов, следуя некоторому конечному простому набору правил из простейших манипуляций. Как, например, алгоритм Евклида. Таким процессам не было чёткого формального определения.
Как описать все функции, которые можно вот так вот, "на листочке", согласно "простым правилам" вычислить за конечное число шагов? Этот вопрос учёные и пытались решить ещё до появления компьютеров. Им было это совсем ещё не понятно.
Как оказалось, они придумали альтернативные описания одного и того же. Я вижу, что ниже уже предложили почитать про тезис Чёрча-Тьюринга, я дополню, что в английской википедии более детально изложено, рекомендую почитать.
И таки-да: любой алгоритм, способный выполняться на этих процессорах ха-ха-ха... кхе-кхе... "полон по Тьюрингу".
Да, вы правильно понимаете, что обсуждаемые нами вещи напрямую связаны с Тьюринг-полнотой. Но фраза "алгоритм полон по Тьюрингу" не имеет совершенно никакого смысла. Полнота по Тьюрингу - это свойство вычислителей, то есть систем из "языка" и "исполнителя", в нашем смысле это язык программирования со своим компилятором и/или интерпретатором. Полнота по Тьюрингу означает, что на языке программирования можно записать любую программу, которая записывается в машинах Тьюринга. Или в лямбда-исчислении Чёрча. Или в общерекурсивных функциях Гёделя. И, в обратную сторону, программу на вашем полном по Тьюрингу языке можно переписать в машину Тьюринга или в программу лямбда-исчисления.
Если откорректировать ваше высказывание, то оно будет звучать как "Любую программу, которую способны выполнить эти процессоры, можно переписать в машину Тьюринга". Вы можете удивиться, но можно даже построить одну машину Тьюринга (зависящую лишь от архитектуры процессора), которая на вход будет ещё принимать машинный код (ассемблер) этой самой программы, и будет исполнять его так, как надо. Таким образом, машина Тьюринга становится исполнителем, а язык программирования - не меняется. В этом плане процессоры, конечно, менее мощны вычислительно, чем машины Тьюринга, с точки зрения математики - у них конечная память =)
считаю нужным отметить, что машины Тьюринга неспроста стали основной теоретической моделью вычислений.
можно поспорить о том, что МТ проще и/или изящнее. но дело не в этом. в отличие от двух упомянутых альтернатив, МТ совершенно естественно позволяет математически определить используемые программой ресурсы - время и память. это ровно то, что позволило в то время сменить парадигму теории вычислений.
в МТ используемая память оценивается самой дальней позицией головки. сравните с лямбда-исчислением - попробуйте придумать, как там оценить используемую алгоритмом память :)
к современным компьютерам модель МТ, по-моему, подходит всё ещё удачно. основное отличие - в современных компьютерах у нас имеется (почти) произвольный доступ к (почти) произвольным ячейкам памяти.
Information
Rating
Does not participate
Location
Санкт-Петербург, Санкт-Петербург и область, Россия
Представьте себе, лямбда-исчисление не зря называется "исчисление". Лямбда-исчисление задаёт такую же систему, как, например, язык Python и его интерпретатор. Представьте себе, любую программу на Python, которая вычисляет натуральное f(x) по x, можно записать в виде лямбда-выражения! Это и есть "программный код" в современном смысле. С помощью правила бета-редукции вы уже "исполняете" этот самый программный код.
Для вас же сейчас очевидно, что МТ - это совсем понятное описание компьютера, а лямбда-исчисление, как вам кажется, "просто способ записи функций". Но это не так. Это альтернативы описания одного и того же. В современном понимании - "программ" и их "исполнителей".
В том и дело, что Чёрч, Тьюринг и другие рассуждали о вычислениях ещё до появления компьютеров, то есть, "автоматических вычислителей". Они пытались формализовать концепцию того, что, грубо говоря, можно вычислить на бумаге за конечное число шагов, следуя некоторому конечному простому набору правил из простейших манипуляций. Как, например, алгоритм Евклида. Таким процессам не было чёткого формального определения.
Как описать все функции, которые можно вот так вот, "на листочке", согласно "простым правилам" вычислить за конечное число шагов? Этот вопрос учёные и пытались решить ещё до появления компьютеров. Им было это совсем ещё не понятно.
Как оказалось, они придумали альтернативные описания одного и того же. Я вижу, что ниже уже предложили почитать про тезис Чёрча-Тьюринга, я дополню, что в английской википедии более детально изложено, рекомендую почитать.
Да, вы правильно понимаете, что обсуждаемые нами вещи напрямую связаны с Тьюринг-полнотой. Но фраза "алгоритм полон по Тьюрингу" не имеет совершенно никакого смысла. Полнота по Тьюрингу - это свойство вычислителей, то есть систем из "языка" и "исполнителя", в нашем смысле это язык программирования со своим компилятором и/или интерпретатором. Полнота по Тьюрингу означает, что на языке программирования можно записать любую программу, которая записывается в машинах Тьюринга. Или в лямбда-исчислении Чёрча. Или в общерекурсивных функциях Гёделя. И, в обратную сторону, программу на вашем полном по Тьюрингу языке можно переписать в машину Тьюринга или в программу лямбда-исчисления.
Если откорректировать ваше высказывание, то оно будет звучать как "Любую программу, которую способны выполнить эти процессоры, можно переписать в машину Тьюринга". Вы можете удивиться, но можно даже построить одну машину Тьюринга (зависящую лишь от архитектуры процессора), которая на вход будет ещё принимать машинный код (ассемблер) этой самой программы, и будет исполнять его так, как надо. Таким образом, машина Тьюринга становится исполнителем, а язык программирования - не меняется. В этом плане процессоры, конечно, менее мощны вычислительно, чем машины Тьюринга, с точки зрения математики - у них конечная память =)
считаю нужным отметить, что машины Тьюринга неспроста стали основной теоретической моделью вычислений.
можно поспорить о том, что МТ проще и/или изящнее. но дело не в этом. в отличие от двух упомянутых альтернатив, МТ совершенно естественно позволяет математически определить используемые программой ресурсы - время и память. это ровно то, что позволило в то время сменить парадигму теории вычислений.
в МТ используемая память оценивается самой дальней позицией головки. сравните с лямбда-исчислением - попробуйте придумать, как там оценить используемую алгоритмом память :)
к современным компьютерам модель МТ, по-моему, подходит всё ещё удачно. основное отличие - в современных компьютерах у нас имеется (почти) произвольный доступ к (почти) произвольным ячейкам памяти.