Что такое машина Тьюринга и какое отношение она имеет к программированию?

Question

[tef]

Машина Тьюринга. Бесконечная лента. Головка, которая может перемещаться, записывать и считывать. Окей. Для чего это всё и что это вообще всё значит?

Answer 1

[Mrrl]

В первую очередь - это формальное определение алгоритма. Задача считается алгоритмически разрешимой тогда и только тогда, когда её решение можно запрограммировать на машине Тьюринга (или каким-нибудь другим эквивалентным способом). Это определение даёт, например, возможность предъявить алгоритмически неразрешимые задачи. Позволяет ввести понятие "Тьюринг-полного" языка - если на языке можно реализовать машину Тьюринга, то на нём можно написать любой алгоритм (язык С таким не является, а C# - является).
В общем, МТ - способ определить некоторый класс алгоритмов:
- некоторые задачи можно решить конечным автоматом;
- для некоторых потребуется конечный автомат со стековой памятью;
- для других достаточно машины Тьюринга;
- для остальных требуется божественное откровение или другие неалгоритмизируемые методы.

Comments

[vaut]

Почему С не "Тьюринг-полный"?
Что, к примеру, в этой https://github.com/cykerway/Turing реализации не работает?

[Армянское Радио]

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

Вот C++ в этом смысле - полный по Тьюрингу (на шаблонах), а C++11 - аж два раза (на шаблонах и constexpr)

[Армянское Радио]

vaut: Вы не сможете записать на C программу, которая во время трансляции, например, посчитает факториал числа.
Сам C, как формальная система обозначений, полнотой по Тьюрингу не обладает.

[Mrrl]

vaut: К сожалению, в C существует значение выражения sizeof(char*). Оно даёт ограничение на размер доступной памяти, и, соответственно, на длину ленты. И какой бы компилятор с C на любой компьютер - и даже на машину Тьюринга, у которой память бесконечна - вы не написали, создать программу, которая после компиляции сможет работать с бесконечной лентой, не удастся.
Вот в C#, если не пользоваться unsafe режимом, обратиться к памяти по явному адресу не получится. Поэтому, формально, можно создать односвязный список сколь угодно большой длины. А для машины Тьюринга большего и не надо.

[vaut]

Армянское Радио спасибо, уточнение меняет суть.

[B@rmaley.e><e]

Mrrl: эта конструкция может возвращать что угодно в случае бесконечной памяти (уверен, её стоило бы назвать UB в таком случае). Кажется, ничто не мешает использовать asm-вставки для работы с памятью.

[Mrrl]

B@rmaley.e><e: Интересно, как будут выглядеть asm-вставки для компилятора с C на МТ. Или какой будет система адресации в процессоре, работающем с бесконечной памятью.

Answer 2

[Moskus]

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

Answer 3

[Армянское Радио]

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

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

Answer 4

[Дмитрий]

Странно что Вы вообще к компьютеру не докапываетесь. Ведь по сути любое вычислительное устройство это 2 инструкции. Одна из них NOT , а другая либо AND либо OR. Вот на этих двух NAND или NOR строится ВСЕ вычислительные устройства!

Comments

[Сергей]

Вообще-то можно и проще. Достаточно одного XOR :) и из этого строится все остальное.

[Mrrl]

Сергей: Кроме XOR нужна загрузка константы 1. Иначе в ситуации, когда вся память заполнена нулями, вы ничего не сможете сделать. Вот с помощью NAND можно получить что угодно из чего угодно.

[B@rmaley.e><e]

Сергей: Вы, видимо, путаете NOR и XOR. NOR (aka Стрелка Пирса), как и NAND (aka Штрих Шеффера), является базисом в пространстве логических функций двух переменных. XOR же таковым являться не может. Более того, никакие другие операторы кроме NAND и NOR не являются базисами (см. критерий Поста).

[Сергей]

Спасибо за ликбез. За давностью лет запамятовал :)

Answer 5

[Оптимус Пьян]

Ну фильм же недавно вышел Игра в имитацию - весь фильм об этой машине. Посмотрите и всё поймёте. А к программированию, на мой взгляд тут уместно только одно слово - алгоритмы!

Comments

[ManWithBear]

Дмитрий в фильме эта машина никак не объяснялась. Просто машина. Так что неудачный пример.

Answer 6

[kykyryky]

МТ дает представление о том, что такое алгоритм.

Answer 7

[uvelichitel]

Этим взламывалась enigma во Вторую Мировую. На этом основана архитектура фон Неймана на которой был построен ENIAC и все компьютеры после. Это расширение конечного автомата, которым прошит любой контроллер, которое реализовано в любом парсере, лексере и компиляторе.

Comments

[Mrrl]

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