Машина Тьюринга по сравнению с машиной Von Neuman
Фон
Архитектура фон Неймана описывает компьютер сохраненной программы, где инструкции и данные хранятся в памяти и работах машины путем изменения ее внутреннего состояния, т.е. инструкция воздействует на некоторые данные и изменяет данные. Так по сути существует состояние, сохраняемое в системе.
Архитектура Машины Тьюринга работает путем управления символами на ленте. т.е. лента с бесконечным числом слотов существует, и в любом моменте времени, Машина Тьюринга находится в конкретном слоте. На основе чтения символа в том слоте машина может изменить символ и переместиться в другой слот. Все это детерминировано.
Вопросы
Есть ли между этими двумя моделями какое-либо отношение? Действительно ли Von Neuman был основан на модели на или вдохновил моделью Turing?
Мы можем сказать, что модель Turing является надмножеством модели Von Newman?
Функциональное программирование вписывается в модель Turing? Если так, как? Я предполагаю, что функциональное программирование не предоставляет себя приятно модели Von Neuman.
5 ответов
Машины Тьюринга - это теоретические концепции, изобретенные для математического исследования области вычислимых проблем и получения способов описания этих вычислений.
Архитектура Фон-Неймана - это архитектура для построения реальных компьютеров (которые реализуют то, что машина Тьюринга описывает теоретически).
Функциональное программирование основано на лямбда-исчислении, которое является другим методом описания вычислений или - более точно - вычислимых функций. Хотя в нем используется совершенно другой подход, он не уступает по мощности машине Тьюринга (говорят, что он тьюринговый полный).
Каждая программа (терм) лямбда-исчисления T записывается просто с помощью комбинации
- переменных, таких как
x - анонимных функций, таких как
λx. T - приложения функций
T T
Несмотря на отсутствие статичности, этого достаточно для любого вычисления, которое может выполнить компьютер. Машины Тьюринга и лямбда-термины могут эмулировать друг друга, а компьютер Фон-Неймана может выполнять и то, и другое (за исключением технических ограничений, таких как обеспечение бесконечного хранения данных, что может потребоваться машине Тьюринга).
Но из-за своей безстатусной и более абстрактной природы функциональные программы могут быть менее эффективными и менее "интуитивными" на компьютерах Фон-Неймана по сравнению с императивными программами, которые следуют его стилю двоичного кода, памяти и обновления.
Модель Тьюринга определяет вычислительные возможности, не углубляясь в реализацию, никто когда-нибудь создаст компьютер, который будет в буквальном смысле похож на машину Тьюринга. (Кроме энтузиастов http://www.youtube.com/watch?v=E3keLeMwfHY ).
Модель Тьюринга не является архитектурой .
Фон Нейман - это руководство по созданию компьютеров. Это ничего не говорит о вычислительных возможностях. В зависимости от набора инструкций созданный компьютер может быть или не быть полным по Тьюрингу (средства могут решать те же задачи, что и машина Тьюринга)
Функциональное программирование (лямбда-исчисление) - это еще одна вычислительная модель, которая является полной по Тьюрингу, но не может быть встроена в систему Фон. Архитектура Неймана.
Обычно речь идет об архитектуре Фон Неймана , в отличие от архитектуры Гарварда . В первом случае код и данные хранятся одинаково, а во втором - отдельные каналы памяти и шины для кода и данных. Все современные настольные ПК - фон Неймана, большинство микроконтроллеров - Harvard. Оба являются примерами реальных проектов, которые пытаются имитировать теоретическую машину Тьюринга (что невозможно, поскольку настоящая машина Тьюринга требует бесконечной памяти).
Я не знаю, какие исторические отношения существуют между машинами Тьюринга и архитектурами фон Неймана. Однако я уверен, что фон Нейман знал о машинах Тьюринга, когда разрабатывал архитектуру фон Неймана.
Однако с точки зрения вычислительных возможностей машины Тьюринга и машины фон Неймана эквивалентны. Любой из них может эмулировать другой (IIRC, эмуляция программы фон Неймана на машине Тьюринга - это операция O (n ^ 6)). Функциональное программирование в форме лямбда-исчисления также эквивалентно. Фактически, все известные вычислительные структуры, по крайней мере столь же мощные, как машины Тьюринга, эквивалентны:
- Машины Тьюринга
- Лямбда-исчисление (функциональное программирование)
- Машины фон Неймана
- Частично рекурсивные функции
Нет никакой разницы в наборе функций, которые могут быть вычислены с помощью любой из этих моделей.
Функциональное программирование происходит от лямбда-исчисления, поэтому оно не отображается напрямую ни на машины Тьюринга, ни на машины фон Немуана. Любой из них может запускать функциональные программы, однако, посредством эмуляции. Я думаю, что отображение для машин Тьюринга, вероятно, более утомительно, чем отображение для машин фон Неймана, поэтому мой ответ на третий вопрос будет «нет, на самом деле это хуже».
"Модель Тьюринга" вовсе не является архитектурной моделью. Это была просто несуществующая машина, которая, по гипотезе Тьюринга, должна была служить средством для доказательства проблемы принятия решения.