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

42

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

Рахул
источник
7
@Kaveh Люди обычно говорят, что да, компьютеры, используемые на практике, являются FSM, но FSM слишком велики, и в представлении FSM теряются интересные структурные свойства. Я никогда не видел объяснений, не связанных с волнами. Поэтому вопрос здесь по теме.
Мартин Бергер
15
Реальный вопрос в том, зачем изучать машины Тьюринга, когда мы используем модель ОЗУ, когда анализируем алгоритмы.
Юваль Фильмус
39
Потому что иногда является лучшим приближением к чем . 10000000000000000000000000000000 100000000000000000000000000000001000000000000000000000000000000010000000000000000000000000000000
Андрей Бауэр
30
Помните, самая известная нерешенная проблема в теоретической информатике сегодня такова: может ли физически невозможный воображаемый компьютер решать проблемы так же быстро, как даже физически невозможный воображаемый компьютер ? Не путайте теоретическую информатику с практической компьютерной инженерией; детали физического мира не особенно актуальны.
Эрик Липперт
23
Реальные материалы состоят из атомов и имеют дискретный характер, так зачем изучать интегралы?
Питер Шор

Ответы:

32

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

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

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


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

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

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

chazisop
источник
4
Вторая часть этого ответа неверна. Компьютеры являются конечными автоматами, даже если вы купили всю оперативную память и другое оборудование, которое могли. Объем оперативной памяти, которую вы можете подключить к компьютеру, ограничен шириной его адресной шины, и то же самое относится к дискам и другим периферийным устройствам.
Эмиль Йержабек поддерживает Монику
12
@ EmilJeřábek не соответствует действительности. Последовательные интерфейсы не имеют адресной шины, и объем данных, к которым я могу получить доступ в Интернете, не ограничен какими-либо свойствами моего компьютера.
Стоп Harm Моника
5
@OrangeDog, но вселенная по-прежнему будет ограничивать объем данных, которые могут храниться в наблюдаемой вселенной
странный урод
9
@ratchetfreak, как демонстрирует машина Тьюринга, вам нужен только локальный доступ - текущий «конец» ленты не обязательно должен находиться в наблюдаемой вселенной;)
Stop Harming Monica
6
Говоря об истории, стоит процитировать рецензию Черри на статью Тьюринга о том, что машины Тьюринга имеют «преимущество в том, что идентификация с эффективностью ... очевидна сразу». То есть для людей, пытающихся убедить себя, что они действительно захватили все, что можно вычислить, определение Тьюринга было убедительным.
Джим Хефферон
44

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

Денис
источник
14
Это ИМХО правильный ответ. Причины сугубо прагматичны: машины Тьюринга лучше, чем конечные автоматы, объясняют, что делают компьютеры в соответствующих масштабах.
Эмиль Йержабек поддерживает Монику
3
Я согласен с этим, за исключением предложения «вы обычно предполагаете, что вы не будете ограничены общим объемом пространства на компьютере». Напротив, почти любая нетривиальная программа ограничена доступным пространством, и программисты идут на все, чтобы с ней справиться (например, сборка мусора для автоматического повторного использования памяти), но (1) мы ничего не можем с этим поделать, и (2) мы ограничиваемся достаточно маленькими входами. Следует отметить, что ТМ дают нам естественное представление о размере проблемы, и что алгоритмы имеют тенденцию быть замкнутыми вниз по отношению к этому естественному представлению о размере проблемы.
Мартин Бергер
2
@MartinBerger Re «практически любая нетривиальная программа ограничена доступным пространством, и программисты идут на все, чтобы с ней справиться (например, сборка мусора для автоматического повторного использования памяти)»: я бы сказал, что программы, написанные для систем с сборкой мусора, учитывают эта система, включая gc , как машина, против которой они программируют. Сборщик мусора не является частью программы; это часть усилий, направленных на то, чтобы точно сказать, что сказал Денис: машина для программирования, в которой практически неограниченные ресурсы памяти.
Питер - Восстановить Монику
2
@ PeterA.Schneider Я вроде не согласен. Причиной использования GC, предоставляемой языковой средой исполнения, является одна из экономических причин разработки программного обеспечения: механизм управления памятью для конкретной программы более производительный, чем GC, и большинство программистов предпочли бы его, если бы они могли безопасно и дешево его осуществить. Но они не могут, так что играйте безопасно и используйте окружающий GC, стоимость которого амортизируется по большому количеству программ. В этом смысле использование GC будет иметь большое значение для работы с памятью конечности.
Мартин Бергер,
2
Машины Тьюринга - это не абстракция того, что делают компьютеры, это абстракция того, что делают компьютеры, и компьютеры были созданы после этого. Компьютеры выполняют большинство своих вычислений, используя фиксированный объем внутренней рабочей памяти, но машины Тьюринга не были изобретены для рассуждений о вычислениях с ограниченным объемом рабочей памяти.
reinierpost
10

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

1000000000000000000000000000000010000000000000000000000000000000

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

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

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

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

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

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

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

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

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

Эрик Аллендер
источник
6

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

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

N22N

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

Эрик Тауэрс
источник
3
Это полезный подход для интуитивного понимания разных уровней «вычислительной мощности». Однако OP, похоже, считает, что реальные компьютеры являются FSM, потому что количество состояний ограничено, например, из-за ограниченного объема ОЗУ. По вашему аргументу, это означает, что реальные компьютеры больше похожи на автоматы, чем на машины Тьюринга, потому что я не могу свободно удвоить число состояний в моделируемой машине; У меня нет бесконечной ленты для хранения.
Амон
1
У машин Тьюринга также не должно быть бесконечной ленты. Компьютеры могут использовать произвольно большой объем внешней памяти в своих вычислениях (и это становится особенно легко с облачными провайдерами, которые у нас есть сегодня), поэтому они в основном похожи на машины Тьюринга, а не на автоматы.
reinierpost
1
Если мы предположим, что у компьютера фиксированный объем памяти, ему не хватит памяти при моделировании компьютера с большим объемом памяти, поэтому при таком предположении он не является действительно универсальным.
Каве
3

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

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

Anoe
источник
Речь идет об отношении модели машины Тьюринга к реальным компьютерам. Если предположить, что у компьютера фиксированный объем памяти, это не совсем универсально.
Каве
1

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

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

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

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

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

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

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

MVG
источник
1

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

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

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

Петерис
источник
1

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

NN2

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

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

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

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

Джесси Энджаян
источник