Что такое полный тьюринг?

Введение[править]

Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.

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

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

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

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

Тьюринговская трясина[править]

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

Первыми представителями «трясины» были лямбда-исчисление, комбинаторная логика и сама машина Тьюринга.

Многие эзотерические языки программирования также являются «трясинами Тьюринга» (напр. Brainfuck, Spoon, Malbolge, Whitespace).

Теорема Геделя о неполноте[править]

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

Кому и зачем нужен язык ассемблера?

Даже из нашего примера «Hello, World!» видно, что ассемблер не так удобен в разработке, как языки высокого уровня. Больших программ на этом языке сейчас никто не пишет, но есть области, где он незаменим:

• На ассемблере разрабатывают встроенные программы для микроконтроллеров. Это миниатюрные компьютеры, установленные в системах сигнализации, пультах управления, датчиках, бытовой технике, модемах и во многих других устройствах. Микроконтроллеры используются даже в робототехнике и спутниковых навигационных системах. Объём памяти у этих мини-компьютеров ограничен, а ассемблер удобен для их программирования тем, что одна его команда транслируется в одну команду в двоичном коде. По исходному тексту программы можно определить время её исполнения и объём памяти для её хранения.
• На ассемблере пишут драйверы устройств и некоторые компоненты операционных систем — например, ядро или загрузчик. Любительские операционные системы MenuetOS и KolibriOS полностью написаны на ассемблере. Ассемблерный код есть в программах для игровых приставок и мультимедийных кодеков.
• Ассемблер применяется в реверс-инжиниринге — обратной разработке программ. Реверс-инжиниринг используют, чтобы понять, как работают программы, какой у них алгоритм. Это нужно в тех случаях, когда создатель по каким-то причинам не хочет публиковать исходный код. Обратной разработкой занимаются антивирусные компании, исследующие вирусы и трояны, создатели драйверов и операционных систем, а также просто любопытные. Ещё её активно применяют компьютерные злоумышленники всех мастей: взламывают программы, ищут уязвимости, пишут вирусы, генераторы ключей и тому подобное.

Нематематическое использование

В разговорном использовании термины “Turing-complete” или “Turing-equivalent” используются для того, чтобы означать, что любой реальный компьютер общего назначения или компьютерный язык может приблизительно имитировать вычислительные аспекты любого другого реального компьютера общего назначения или компьютерного языка.
Реальные компьютеры, построенные до сих пор, могут быть функционально проанализированы как одноканальная машина Тьюринга (“лента”, соответствующая их памяти), таким образом, связанная с ними математика может быть применена путем абстрагирования их работы достаточно далеко. Однако реальные компьютеры имеют ограниченные физические ресурсы, поэтому они являются только линейными ограниченными автоматами. Напротив, универсальный компьютер определяется как устройство с набором инструкций Тьюринга, бесконечной памятью и бесконечным доступным временем.

Тьюринг-полнота и неполнота некоторых языков программирования [ править ]

Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить на нём интерпретатор Тьюринг-полного языка.

Assembly language

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

Всё необходимое для машины Тьюринга на asm можно сделать примерно так:

И далее использовать инструкцию \mathrm или ей подобную, чтобы выполнять определённую последовательность команд при определённом текущем значении, таким образом обеспечив ветвление.

C

В языке C нет высокоуровневого понятия переменной (в смысле Паскаля), есть объекты (object), хранящиеся в памяти как последовательно расположенные байты,имеющие адрес (байты в свою очередь состоят из неадресуемых битов). Целые типы ограничены (конечное множество значений), указатель отождествляется с адресом, постулируется возможность хранить адрес в целочисленной переменной (int или long — зависит от реализации), откуда следует ограниченность множества значений указателей, а стало быть, и ограниченность адресного пространства C-машины. То есть язык C, как и язык ассемблера, ориентирован на архитектуру с конечной памятью. Файл не является типом данных языка C, в отличие от Паскаля. Это вещь из окружения, для работы с которой есть операции над потоками в виде набора библиотечных функций. Тип fpos_t, принятый в стандарте C для позиционирования файлов, постулируется как «отличный от массива тип данных (object type)». Следовательно, множество значений этого типа конечно, а значит, максимальная длина файла в языке C ограничена сверху.

HTML

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

Некоторые другие ЯП

Нематематическое использование [ править ]

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

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

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

Для того, чтобы представить простейшую машину Тьюринга, взглянем на её художественную реализацию:

Это бесконечная лента, не имеющая ни начала, ни конца, поделённая на ячейки. Для работы с ней мы используем некое управляющее устройство (автомат), для визуализации выбрана каретка. В каждый момент времени она имеет состояние qj и считывает содержимое ячейки ai. О том, что происходит в остальной части ленты, каретка не знает, соответственно оперировать она может только текущими данными. Всего возможно три типа действий, зависящий от этой композиции:

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

Создадим таблицу для реализации алгоритма Тьюринга:

Символами _Л, _П, _Н обозначим направление движения автомата – соответственно сдвиг «влево», «вправо» или неподвижное положение.

Пусть наша лента выглядит так:

Начальное положение – крайняя правая ячейка, остановка – в пустой клетке. Догадались как она будет выглядеть после завершения алгоритма?

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

Примечания и ссылки

Рекомендации

1. (in) Джон К. Митчелл, Концепции языков программирования , Издательство Кембриджского университета ,2003 г. , стр.  14 :
2. (in) Брюс Дж. Макленнан, Принципы языков программирования , Oxford University Press ,1999 г., Введение: Что такое язык программирования? :
3. (in) , В стеке обмена На заданный вопрос выбранный ответ предполагает, что полнота по Тьюрингу не требуется для того, чтобы рассматривать язык как язык программирования.
4. Пример реализации машины Тьюринга на C: (ru) Хуан Пабло Ринальди (juampi), , на GitHub ,13 января 2014 г.(по состоянию на 21 мая 2019 г. ) .
5. .
6. (in) Эли и Джонас, на Accodeing to you (по состоянию на 17 мая 2019 г. ) .
7. .
8. Бенджамин Вернер, «  Множества в типах, типы в множествах  », Труды TACS’97 ,1997 г..
9. , на www.themarysue.com ,16 апреля 2010 г..
10. Пол Ренделл , , на rendell-attic.org ,12 января 2005 г..
11. (in) Алекс Черчилль , , Корнельский университет ,23 апреля 2019.
12. (in) Gunivers, , на YouTube ,17 июля 2019 г.,(по состоянию на 6 мая 2020 г. ) .
13. (in) Том Вилденхейн, на ,16 марта 2017 г.(по состоянию на 10 июля 2020 г. )
14. (in) Хаббо (@Habbo): , В Твиттере ,9 ноября 2020 г.(по состоянию на 30 ноября 2020 г. )

Как устроен язык ассемблера?

Ассемблер можно считать языком второго поколения, если за первый принять машинный язык. Он работает непосредственно с процессором, и каждая его команда — это инструкция процессора, а не операционной или файловой системы. Перевод языка ассемблера в машинный код называется ассемблированием.

Команды ассемблера состоят из кодов операций и операндов. Операнды — это адреса, из которых процессор будет брать данные для вычислений и в которые будет помещать результат. Адресами могут быть ячейки оперативной памяти и регистры — память внутри процессора. Процессор работает с регистрами гораздо быстрее, чем с оперативной памятью.

Коды операций в языке ассемблера мнемонические, то есть удобные для запоминания:

• ADD — сложение (от англ. addition);
• SUB — вычитание (от англ. subtraction);
• MUL — умножение (от англ. multiplication) и так далее.

Регистрам и ячейкам памяти присваиваются символические имена, например:

EAX, EBX, AX, AH — имена для регистров;

meml — имя для ячейки памяти.

Например, так выглядит команда сложения чисел из регистров AX и BX:

add ax, bx

А это команда вычитания чисел из регистров AX и BX:

sub ax, bx

Кроме инструкций, в языке ассемблера есть директивы — команды управления компилятором, то есть программой-ассемблером.

Вот некоторые из них:

• INCLUDE — открыть файл и начать его компиляцию;
• EXIT — прекратить компиляцию файла;.
• DEF — назначить регистру символическое имя и т. д.

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

Вот, например, код, на ассемблере, выводящий на экран цифры от 1 до 10:

Здесь действие будет выполняться в цикле — как, например, в циклах for или do while в языках высокого уровня.

Единого стандарта для языков ассемблера нет. В работе с процессорами Intel разработчики придерживаются двух синтаксисов: Intel и AT&T. Ни у того ни у другого нет особых преимуществ: AT&T — стандартный синтаксис в Linux, а Intel используется в мире Microsoft.

Одна и та же команда в них выглядит по-разному.

Например, в синтаксисе Intel:

mov eax, ebx — команда перемещает данные из регистра eax в регистр ebx.

В синтаксисе AT&T эта команда выглядит так:

Примеры

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

• Теория автоматов
• Формальная грамматика (генераторы языков)
• Формальный язык (распознаватели языка)
• Лямбда-исчисление
• Машины Пост-Тьюринга
• Расчет процесса

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

• Все универсальные языки широко используются.
  • Языки процедурного программирования, такие как C , Pascal .
  • Объектно-ориентированные языки, такие как Java , Smalltalk или C # .
  • Multi-парадигме языков , таких как Ada , C ++ , Common Lisp , Fortran , Object Pascal , Perl , Python , R .
• Большинство языков, использующих менее распространенные парадигмы:
  • Функциональные языки, такие как Lisp и Haskell .
  • Языки логического программирования, такие как Пролог .
  • Макропроцессор общего назначения, например m4 .
  • Декларативные языки, такие как XSLT .
  • VHDL и другие языки описания оборудования.
  • TeX , система набора.
  • Эзотерические языки программирования , форма математического отдыха, в которой программисты решают, как создавать базовые программные конструкции на чрезвычайно сложном, но математически эквивалентном Тьюрингу языке.

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

Полнота по Тьюрингу — это абстрактное утверждение способности, а не рецепт конкретных языковых функций, используемых для реализации этой способности. Функции, используемые для достижения полноты по Тьюрингу, могут быть совершенно разными; Системы Fortran будут использовать конструкции цикла или, возможно, даже операторы goto для достижения повторения; В Haskell и Prolog, в которых почти не было цикла, использовалась бы рекурсия . Большинство языков программирования описывают вычисления на архитектурах фон Неймана , которые имеют память (RAM и регистр) и блок управления. Эти два элемента делают эту архитектуру полной по Тьюрингу. Даже чистые функциональные языки являются полными по Тьюрингу.

Полнота по Тьюрингу в декларативном SQL реализуется с помощью рекурсивных общих табличных выражений . Неудивительно, что процедурные расширения SQL ( PLSQL и т. Д.) Также являются полными по Тьюрингу. Это иллюстрирует одну причину, по которой относительно мощные неполные по Тьюрингу языки встречаются редко: чем мощнее язык изначально, тем сложнее задачи, к которым он применяется, и тем скорее его недостаточная полнота воспринимается как недостаток, поощряя его использование. расширение, пока оно не станет полным по Тьюрингу.

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

Правило 110 и игры Конвея жизни , как клеточные автоматы , являются Тьюринг.

Непреднамеренная полнота по Тьюрингу

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

Программное обеспечение:

• Microsoft Excel
• Microsoft PowerPoint

Видеоигры:

• Крепость гномов
• OpenTTD [ необходима ссылка ]
• Terraria [ необходима ссылка ]
• Minecraft [ самостоятельно опубликованный источник ]
• Сапер
• LittleBigPlanet
• Баба — это ты
• Факторио
• Города: горизонты
• Opus Magnum
• Портал 2 [ самостоятельно опубликованный источник ]
• Шэньчжэнь I / O

Социальные медиа:

Отель Хаббо

Карточные игры:

Magic: The Gathering

Игры с нулевым лицом (симуляторы):

Игра жизни Конвея

Вычислительные языки:

Шаблоны C ++

Компьютерное железо:

инструкция x86 MOV

Биология:

Сети химических реакций и ферментные ДНК-компьютеры оказались эквивалентными по Тьюрингу

Тест по Тьюрингу

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

Такой тест на долгие годы предопределил развитие ИИ – программы вроде Элизы или PARRY строились именно на копировании человеческого поведения машиной. Уже позднее, когда стало понятно, что путь тупиковый, вектор развития был сдвинут в сторону изучения механизмов интеллекта. Однако до сих пор тема «способна ли мыслить машина» лежит в основе многих тестов, романов и кинофильмов.

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

Тест по Тьюрингу

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

Такой тест на долгие годы предопределил развитие ИИ – программы вроде Элизы или PARRY строились именно на копировании человеческого поведения машиной. Уже позднее, когда стало понятно, что путь тупиковый, вектор развития был сдвинут в сторону изучения механизмов интеллекта. Однако до сих пор тема «способна ли мыслить машина» лежит в основе многих тестов, романов и кинофильмов.

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

Тьюринг +

Turing + (Turing Plus) — это язык параллельного системного программирования, основанный на языке программирования Turing, разработанный Джеймсом Корди и Риком Холтом , затем в Университете Торонто , Канада, в 1987 году. Некоторые, но не все, функции Turing + были в конечном итоге включены в объектно-ориентированный тьюринг . Тьюринг + расширенный исходный Тьюринг с процессами и мониторами (как указано К. Хоаром ), а также языковые конструкции, необходимые для системного программирования, такие как двоичный ввод-вывод, раздельная компиляция, переменные по абсолютным адресам, преобразователи типов и другие функции.

Turing + был специально разработан для замены Concurrent Euclid в приложениях системного программирования. Операционная система ТУНИСА , изначально написано на Параллельном Евклиде, перекодировались к тьюринговому + в его MiniTunis реализации. Turing + использовался для реализации нескольких производственных программных систем, включая язык программирования TXL .

Ссылки [ править ]

1. ↑ Ходжес, Эндрю (1992) , Алан Тьюринг: Загадка , Лондон: Burnett Books, стр. 111, ISBN 0-04-510060-8
2. ^ Рохас, Рауль (1998). «Как сделать Z3 Цузе универсальным компьютером» . Анналы истории вычислительной техники . 20 (3): 51–54. DOI10.1109 / 85.707574 .
3. ↑ Лайонс, Боб (30 марта 2001 г.). «Универсальная машина Тьюринга в XSLT» . Решения для интеграции B2B от Unidex . Архивировано 17 июля 2011 года . Проверено 5 июля 2010 года .
4. ^ Boyer, Роберт S .; Мур, Дж. Стротер (май 1983 г.). Механическое доказательство полноты Тьюринга чистого Лиспа (Технический отчет). Институт вычислительной техники Техасского университета в Остине. 37. Архивировано из оригинала 22 сентября 2017 года.
5. ^ Dfetter; Брейнбаас (8 августа 2011 г.). «Циклическая система тегов» . PostgreSQL вики . Проверено 10 сентября 2014 года .
6. ^ «Объявление LAMBDA: превратите формулы Excel в пользовательские функции» . TECHCOMMUNITY.MICROSOFT.COM . 3 декабря 2020 . Проверено 8 декабря 2020 .
7. ^ Wildenhain, Том (9 апреля 2020). «О полноте по Тьюрингу MS PowerPoint» .[ самостоятельно опубликованный источник ]
8. ^ Cedotal, Эндрю (16 апреля 2010). «Человек использует самую сложную компьютерную игру в мире, чтобы создать… рабочую машину Тьюринга» . Мэри Сью . Архивировано 27 июня 2015 года . Дата обращения 2 июня 2015 .
9. ^ a b c Цвинкау, Андреас (20 октября 2013 г.). «Случайно полный по Тьюрингу» . Андреас Цвинкау . Архивировано из оригинала на 5 июня 2015 года . Дата обращения 2 июня 2015 .[ самостоятельно опубликованный источник ]
10. ↑ Кэй, Ричард (31 мая 2007 г.). «Бесконечные версии тральщика являются полными по Тьюрингу» . Страницы Сапера Ричарда Кея . Архивировано 2 февраля 2017 года . Проверено 14 марта 2017 года .[ самостоятельно опубликованный источник ]
11. ^ «БАБА ЗАВЕРШАЕТСЯ: Эскиз доказательства (v2)» . 25 марта 2019 . Дата обращения 2 июня 2020 .
12. ^ «Твит Мэтью Родригеса (@ mattar0d) видео, демонстрирующего реализацию правила 110 сотового автомата в Baba Is You» . 25 марта 2019 . Дата обращения 2 июня 2020 .
13. ^ «Я сделал программируемый полный компьютер по Тьюрингу в Factorio» . Reddit . 31 января 2016 . Дата обращения 2 февраля 2020 .
14. ↑ Планкетт, Люк (16 июля 2019 г.). «Cities: Skylines Map становится компьютером с питанием от какашек» . Котаку . Проверено 16 июля 2019 .
15. Рианна Колдуэлл, Брендан (20 ноября 2017 г.). «Игрок Opus Magnum делает алхимический компьютер» . Ружье Rock Paper . Проверено 23 сентября 2019 года .
16. ↑ Татум, Александр (16 июля 2019). «Трехзначный двоичный калькулятор» . Steam . Проверено 1 июля 2019 года .
17. ^ «SHENZHEN I / O — Игра жизни Конвея — YouTube» . www.youtube.com . Проверено 27 декабря 2020 года .
18. ^ «Твиттер Habbo о реализации машины Тьюринга в игре» . 9 ноября 2020 . Проверено 11 ноября 2020 .
19. ↑ Алекс Черчилль; Стелла Бидерман; Остин Херрик (2019). «Magic: The Gathering завершена по Тьюрингу». arXiv1904.09828cs.AI
20. ↑ Ренделл, Пол (12 января 2005 г.). «Машина Тьюринга в игре жизни Конвея» . Ренделл-Чердак . Архивировано 8 июля 2009 года . Проверено 22 июня 2009 года .[ самостоятельно опубликованный источник ]
21. ^ Calcyman; Джонстон, Натаниэль (16 июня 2009 г.). «Спартанский универсальный компьютер-конструктор» . LifeWiki . Проверено 22 июня 2009 года .
22. ^ Мейерс, Скотт (Скотт Дуглас) (2005). Эффективный C ++: 55 конкретных способов улучшить ваши программы и дизайн (3-е изд.). Река Аппер Сэдл, Нью-Джерси: Аддисон-Уэсли. ISBN 0321334876. OCLC  60425273 .
23. ^ См. Историю TMP в Викиучебниках.
24. ^ Долан, Стивен. «mov является полным по Тьюрингу» . stedolan.net . Дата обращения 9 мая 2019 .

Проблема остановки[править]

void g():
   if halts(g):
       for(;;)

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

Для того, чтобы представить простейшую машину Тьюринга, взглянем на её художественную реализацию:

Это бесконечная лента, не имеющая ни начала, ни конца, поделённая на ячейки. Для работы с ней мы используем некое управляющее устройство (автомат), для визуализации выбрана каретка. В каждый момент времени она имеет состояние qj и считывает содержимое ячейки ai. О том, что происходит в остальной части ленты, каретка не знает, соответственно оперировать она может только текущими данными. Всего возможно три типа действий, зависящий от этой композиции:

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

Создадим таблицу для реализации алгоритма Тьюринга:

Символами _Л, _П, _Н обозначим направление движения автомата – соответственно сдвиг «влево», «вправо» или неподвижное положение.

Пусть наша лента выглядит так:

Начальное положение – крайняя правая ячейка, остановка – в пустой клетке. Догадались как она будет выглядеть после завершения алгоритма?

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

Полнота по Тьюрингу

Ещё один важный вопрос, связанный с именем известного математика. На форумах и в статьях вы неоднократно могли видеть выражение «полный\не полный язык программирования по Тьюрингу». Ответ на вопрос «что это означает?» возвращает нас к описанной выше теории. Как уже было сказано, машина Тьюринга позволяет выполнить любое преобразование, соответственно, вы можете реализовать на ней абсолютно любой алгоритм или функцию. То же самое относится и к языкам. Если с его помощью вы можете реализовать любой заданный алгоритм – он тьюринг-полный. Если в дело вступают ограничения синтаксиса или любые физические – не полный.

Критерии Тьюринг-полноты[править]

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

Конечность (нет бесконечных символьных множеств и пр.).

Фиксированное описание (формальность).

Всегда достаточный объём доступной памяти — в идеале здесь имеется в виду неограниченная память, однако физические рамки не позволяют сделать память ЭВМ бесконечной, поэтому она просто должна быть «always big enough».

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

Возможность функциональной композиции (вызов одной функции из другой, рекурсия).

Наличие циклов {\bf while} с прерыванием или эквивалентных им конструкций.

Возможность останавливать выполнение (halt) или каким-то образом подавать сигнал о результатах выполнения.

Представление множества натуральных чисел, понятие нуля и следующего числа. Возможны другие подобные системы.

Поддержка входных и выходных данных (I/O), причём без формальных ограничений в объёме. Очевидно, что если любая программа, написанная на каком-то языке программирования, принимает на вход не более фиксированного n бит данных и возвращает не более n бит, этот язык не может быть Тьюринг-полным.

Где почитать ещё?

1. Фалина И.Н. Тема «Машина Тьюринга» в школьном курсе информатики
   (inf.1september.ru).
2. Майер Р.В. Машины Поста и Тьюринга (komp-model.narod.ru).
3. Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В.
   Машина Тьюринга и алгоритмы Маркова. Решение задач, М.: МГУ, 2006.
4. Бекман И.Н. Компьютерные науки. Лекция 7. Алгоритмы (profbeckman.narod.ru)
5. Соловьев А. Дискретная математика без формул (lib.rus.ec)
6. Ершов С.С. Элементы теории алгоритмов, Челябинск, Издательский центр ЮУрГУ, 2009.
7. Варпаховский Ф.Л. Элементы теории алгоритмов, М: Просвещение, 1970.
8. Верещагин Н.К., Шень А. Вычислимые функции, М: МЦНМО, 1999.