Машина Тьюринга против машины Von Neuman

Фон

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

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

Вопросы

Есть ли какая-либо связь между этими двумя моделями? Была ли модель фон Неймана основана или вдохновлена моделью Тьюринга?
Можно ли сказать, что модель Тьюринга является надмножеством модели фон Ньюмана?
Соответствует ли функциональное программирование модели Тьюринга? Если да, то как? Я предполагаю функциональная программирование не поддается качеству модели Von Neuman.

Ответ 1

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

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

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

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

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

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

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

Ответ 2

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

Ответ 3

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

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

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

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

Ответ 4

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

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

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

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

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

Ответ 5

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