Реальные компьютеры имеют только конечное число состояний, так какова связь машин Тьюринга с реальными компьютерами?

Реальные компьютеры имеют ограниченную память и ограниченное число состояний. Так что они по сути конечные автоматы. Почему теоретические компьютерные ученые используют машины Тьюринга (и другие эквивалентные модели) для изучения компьютеров? Какой смысл изучать эти гораздо более сильные модели по отношению к реальным компьютерам? Почему конечной модели автоматов недостаточно?

При рассмотрении этого вопроса существует два подхода: исторический, который относится к тому, как концепции были обнаружены, и технический, который объясняет, почему некоторые концепции были приняты, а другие были оставлены или даже забыты.

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

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

РЕДАКТИРОВАТЬ: Я рассмотрел оба вопроса, поднятые в комментариях, но решил не включать их краткости и времени, которое у меня было достаточно, чтобы записать ответ. Это мое рассуждение о том, почему я считаю, что эти моменты не уменьшают эффективность машин Тьюринга при моделировании современных компьютеров, особенно по сравнению с конечными автоматами:

• Позвольте мне сначала рассмотреть физическую проблему ограничения памяти вселенной. Прежде всего, мы не знаем, конечна ли Вселенная или нет. Кроме того, концепция наблюдаемой вселенной, которая по определению конечна, также по определению не имеет отношения к пользователю, который может путешествовать в любую точку наблюдаемой вселенной, чтобы использовать память. Причина в том, что наблюдаемая вселенная относится к тому, что мы можем наблюдать из определенной точки, а именно с Земли, и было бы иначе, если бы наблюдатель мог путешествовать в другое место во вселенной. Таким образом, любая аргументация о наблюдаемой вселенной превращается в вопрос о конечности вселенной. Но давайте предположим, что благодаря некоторому прорыву мы приобретаем знание, что вселенная действительно конечна. Хотя это будет иметь большое влияние на научные вопросы, Я сомневаюсь, что это повлияет на использование компьютеров. Проще говоря, в принципе компьютеры могут быть конечными автоматами, а не машинами Тьюринга. Но для абсолютного большинства вычислений и, по всей вероятности, всех вычислений, которые интересуют людей, машины Тьюринга и связанная с ними теория предлагают нам лучшее понимание. В грубом примере, хотя мы знаем, что ньютоновская физика в основном ошибочна, я сомневаюсь, что инженеры-механики используют в основном квантовую физику для проектирования автомобилей или заводских машин; Угловые случаи, когда это необходимо, могут рассматриваться на индивидуальном уровне. Но для абсолютного большинства вычислений и, по всей вероятности, всех вычислений, которые интересуют людей, машины Тьюринга и связанная с ними теория предлагают нам лучшее понимание. В грубом примере, хотя мы знаем, что ньютоновская физика в основном ошибочна, я сомневаюсь, что инженеры-механики используют в основном квантовую физику для проектирования автомобилей или заводских машин; Угловые случаи, когда это необходимо, могут рассматриваться на индивидуальном уровне. Но для абсолютного большинства вычислений и, по всей вероятности, всех вычислений, которые интересуют людей, машины Тьюринга и связанная с ними теория предлагают нам лучшее понимание. В грубом примере, хотя мы знаем, что ньютоновская физика в основном ошибочна, я сомневаюсь, что инженеры-механики используют в основном квантовую физику для проектирования автомобилей или заводских машин; Угловые случаи, когда это необходимо, могут рассматриваться на индивидуальном уровне.

• Любые технические ограничения, такие как шины и адресация, являются просто техническими ограничениями существующего оборудования и могут быть преодолены физически. Причина, по которой это не так для современных компьютеров, заключается в том, что 64-разрядная адресация позволила нам переместить верхнюю границу адресного пространства на несколько высот, если какие-либо приложения могут этого достичь. Кроме того, реализация «расширяемой» системы адресации может потенциально оказать влияние на абсолютное большинство вычислений, которые в ней не нуждаются и, следовательно, неэффективны. Ничто не мешает вам организовать иерархическую систему адресации, например, для двух уровней первый адрес может относиться к любому из банков памяти, а затем каждый банк имеет 2 $2^{64}$$2^{64}$разные адреса. По сути, работа в сети - отличный способ сделать это, каждая машина заботится только о своей локальной памяти, но они могут вычислять вместе.

Чтобы завершить другие ответы: я думаю, что машина Тьюринга - лучшая абстракция того, что делают компьютеры, чем конечные автоматы. Действительно, основное различие между этими двумя моделями заключается в том, что с помощью конечных автоматов мы ожидаем обработки данных, превышающих пространство состояний, а машина Тьюринга является моделью для обратного (пространство состояний >> данные) путем создания состояния пространство бесконечно. Эта бесконечность может быть воспринята как абстракция «очень большая перед размером данных». При написании компьютерной программы вы пытаетесь сэкономить место для повышения эффективности, но обычно предполагаете, что общий объем пространства на компьютере не будет ограничен. Это одна из причин, почему машины Тьюринга являются лучшей абстракцией компьютеров, чем конечные автоматы.

Андрей Бауэр привел в комментариях одну важную причину:

$\infty$$10000000000000000000000000000000$$10000000000000000000000000000000$

Позвольте мне завершить другие ответы некоторыми пунктами, которые, вероятно, были слишком очевидны, чтобы упоминать:

• Если вашей целью является изучение реальных компьютеров, то и конечные автоматы, и машины Тьюринга часто будут слишком простыми моделями для соответствующих вопросов. Реальные компьютеры имеют несколько процессорных ядер с иерархией кэша (или какой-либо другой интеллектуальной схемой управления), имеют доступ к приличному объему быстрой памяти, доступ к огромному количеству медленной внешней памяти (жесткие диски) и могут связываться с другими подобными компьютерами на Скорость примерно сопоставима со скоростью доступа к медленной внешней памяти.
• Если вы теперь спросите себя, зачем вам нужны все эти детали, то окажется, что вашей настоящей целью является изучение проблемных примеров и то, насколько эффективно вы можете их решать. Если вы говорите о реальных компьютерах, это также может означать, что вы проводите эксперименты с фактическими проблемами на разных типах (реальных) компьютерных архитектур.
• Модель реальных компьютеров, описанная выше, все еще идеализирована, потому что она игнорирует различные режимы отказа реальных компьютеров. Поскольку сбой отключения питания может быть более частым, чем сбой жесткого диска (и в любом случае на жестких дисках могут быть резервные копии), некоторые проблемные домены, такие как надежная работа с базой данных, могут принять это во внимание.
• $\Pi_1^0$

Формализм полезен или нет, в зависимости от того, что люди хотят использовать формализм для моделирования и понимания.

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

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

Конечные автоматы также были полезны для понимания сложности схемы; Все эти модели имеют свое место в математическом арсенале.

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

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

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

Фактические компьютеры не являются FSA. Фактический компьютер - это универсальный компьютер, в том смысле, что мы можем описать компьютер для эмуляции компьютера, который будет имитировать компьютер. Для многих примеров, поиск «виртуальная машина».

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

$n$$2^{2^n}$

В качестве отправной точки в литературе я могу порекомендовать « О существовании универсальных конечных автоматов или автоматов Pushdown », в которых изучается несуществование универсальных автоматов. Вы также можете посмотреть его ссылки (и так далее).

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

Будучи механически простым, легко показать, являются ли или в какой степени другие машины эквивалентными машине Тьюринга. Это, в свою очередь, позволяет относительно легко показать, является ли данный компьютер (или компьютерный язык) действительно универсальным (c / f "Turing-complete").

Почему конечной модели автоматов недостаточно?

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

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

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

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

Какой смысл изучать эти гораздо более сильные модели по отношению к реальным компьютерам?

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

Большинство проблем требуют машин Тьюринга конечных размеров

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

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

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

$n$$n\cdot2$

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

Реальные компьютеры имеют ограниченную память и ограниченное число состояний. Так что они по сути конечные автоматы.

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