Практическая значимость машин Тьюринга?

Я инженер-электрик, и у меня был только один курс CS в колледже 26 лет назад. Тем не менее, я также преданный пользователь Mathematica.

У меня есть ощущение, что машины Тьюринга очень важны в информатике. Разве важна только теория информатики? Если есть практические последствия / применения, каковы некоторые из них?

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

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

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

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

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

   Сравните этот аспект с моделью ОЗУ (если она не используется в минималистическом виде): следующая операция может быть любой из нескольких операций, которые могут получить доступ к любым (двум) регистрам. Есть также несколько структур управления.

2. Продолжительность и использование пространства
   Было (только) две основные модели вычислений , которые появились почти одновременно с машинами Тьюринга, а именно Церкви -исчисления$\lambda$ и клейновские -recursive функций$\mu$ . Они ответили на тот же вопрос, который задал Тьюринг - проблема Энтшеидунга Гильберта, - но гораздо менее легко (если вообще) поддаются определению времени выполнения и использования пространства. В каком-то смысле они слишком абстрактны, чтобы быть связанными с более реалистичными моделями машин.

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

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

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

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

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

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

Конечно, вы могли бы также реализовать что-нибудь еще, полное по Тьюрингу (например, C или комбинаторную логику), но иногда машина Тьюринга является самым простым вариантом.

Машина Тьюринга - это математическая модель вычислений. Его преимущества:

1. Проверьте разрешимость Если TM не может решить проблему за счетное время, то не может быть никакого алгоритма, который мог бы решить эту проблему (то есть проблема неразрешима).

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

2. Классифицировать проблему TM помогает классифицировать разрешимые задачи на классы полиномиальной иерархии.

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

3. Разработать и внедрить алгоритм для практических машин ТМ помогает распространять идею алгоритма в других практических машинах. После успешной проверки 1,2 критериев мы можем использовать наши практические устройства / компьютеры для разработки и реализации алгоритма.

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