Машина Тьюринга против машины фон Неймана

Question

Фон

Архитектура Von-Neumann описывает компьютер с хранимой программой, в котором инструкции и данные хранятся в памяти, и машина работает, изменяя свое внутреннее состояние, то есть инструкция работает с некоторыми данными и модифицирует данные. По сути, в системе поддерживается состояние.

Архитектура машины Тьюринга работает путем манипулирования символами на ленте. Т.е. существует лента с бесконечным числом слотов, и в любой момент времени машина Тьюринга находится в определенном слоте. На основании символа, считанного в этом слоте, машина может изменить символ и перейти в другой слот. Все это детерминировано.

---

Вопросы

1. Есть ли связь между этими двумя моделями? Была ли модель фон Неймана основана или вдохновлена ​​моделью Тьюринга?

2. Можно ли сказать, что модель Тьюринга является надмножеством модели фон Ньюмана?

3. Соответствует ли функциональное программирование модели Тьюринга? Если так, то как? Я предполагаю функциональное программирование не подходит для модели фон Неймана.

Answer 1

Машины Тьюринга - это теоретические концепции , изобретенные для математического исследования области вычислимых задач и получения способов описания этих вычислений.

Архитектура фон-Неймана - это архитектура для построения реальных компьютеров (которые реализуют , что теоретически машина Тьюринга описывает).

Функциональное программирование основано на лямбда-исчислении , которое является еще одним методом описания вычислений или, точнее, вычислимых функций. Хотя он использует совершенно другой подход, он одинаково мощен для машины Тьюринга (говорят, что он завершен по Тьюрингу ).

Каждая программа лямбда-исчисления (термин) T написана только с использованием комбинации

• переменные типа x
• анонимные функции, такие как λx. T
• приложения функций T T

Несмотря на отсутствие состояния, этого достаточно для каждого вычисления, которое может выполнить компьютер. Машины Тьюринга и лямбда-выражения могут эмулировать друг друга, и компьютер Von-Neumann может выполнять оба (кроме технических ограничений, таких как предоставление бесконечного хранилища, которое может потребоваться машине Тьюринга).

Но из-за их отсутствия состояния и более абстрактного характера функциональные программы могут быть менее эффективными и менее «интуитивными» на компьютерах Von-Neumann по сравнению с императивными программами , которые следуют стилю двоичного кода, памяти и обновлений.

Answer 2

Обычно речь идет об архитектуре Von Neumann , в отличие от архитектуры Harvard . В первом код и данные хранятся одинаково, а во втором - отдельные пути памяти и шины для кода и данных. Все современные настольные ПК - это фон Нейман, большинство микроконтроллеров - гарвардские. Оба являются примерами реальных проектов, которые пытаются подражать теоретической машине Тьюринга (что невозможно, потому что настоящей машине Тьюринга требуется бесконечная память).

Answer 3

Я не знаю, какие исторические отношения существуют между машинами Тьюринга и архитектурами фон Неймана. Однако я уверен, что фон Нейман знал о машинах Тьюринга, когда разрабатывал архитектуру фон Неймана.

Однако, что касается вычислительных возможностей, машины Тьюринга и машины фон Неймана эквивалентны. Любой из них может эмулировать другой (IIRC, эмуляция программы фон Неймана на машине Тьюринга - операция O (n ^ 6)). Функциональное программирование в форме лямбда-исчисления также эквивалентно. Фактически, все известные вычислительные структуры, по крайней мере, такие же мощные, как машины Тьюринга, эквивалентны:

• машины Тьюринга
• Лямбда-исчисление (функциональное программирование)
• фон фон Неймана
• Частичные рекурсивные функции

Нет разницы в наборе функций, которые можно вычислить с помощью любой из этих моделей.

Функциональное программирование основано на лямбда-исчислении, поэтому оно не отображается напрямую ни на машины Тьюринга, ни на фон Немуана. Любой из них может запускать функциональные программы, однако, через эмуляцию. Я думаю, что сопоставление для машин Тьюринга, вероятно, более утомительно, чем сопоставление для машин фон Неймана, поэтому мой ответ на 3-й вопрос будет «нет, на самом деле это хуже».

Answer 4

Модель Тьюринга определяет вычислительные возможности, не углубляясь в реализацию, никто никогда не создаст компьютер, который буквально будет выглядеть как машина Тьюринга. (Кроме энтузиастов http://www.youtube.com/watch?v=E3keLeMwfHY).

Модель Тьюринга не является архитектурой .

Фон Нейман - руководство по сборке компьютеров. Это ничего не говорит о вычислительных возможностях. В зависимости от набора инструкций полученный компьютер может быть или не быть завершенным по Тьюрингу (средства могут решать те же задачи, что и машина Тьюринга)

Функциональное программирование (лямбда-исчисление) - это еще одна вычислительная модель, которая завершена по Тьюрингу, но не может быть встроена в архитектуру фон Неймана.

Answer 5

«Модель» Тьюринга вовсе не является архитектурной моделью.Это была просто несуществующая машина, которую Тьюринг предположил, чтобы служить транспортным средством для доказательства решения проблемы .