Что такое машина Тьюринга?
Что такое машина Тьюринга и почему люди продолжают упоминать ее? Мой IBM PC - это все, что мне нужно для вычислений! Почему кто-то заботится об этих машинах?
10 ответов
Причина, по которой машины Тьюринга имеют большое значение, связана с изучением классических вещей типа Computing Science или Theory of Computation. В основном речь идет об анализе общих свойств компьютера, таких как теоретические возможности и ограничения компьютера, а также то, что мы имеем в виду, когда говорим о "вычислении" чего-либо.
Одним из примеров того, что можно изучить с помощью машин Тьюринга, является проблема остановки. Хотя эта проблема является чем-то вроде академического упражнения, она имеет вполне ощутимые практические последствия. Почему бы не написать отладчик, который просто скажет вам, содержит ли ваша программа бесконечные циклы? Задача Остановки устанавливает, что решение этой проблемы для общего случая невозможно.
Изучение машин Тьюринга также позволяет изучать грамматики языка и их классы, что приводит к развитию языка программирования. Термин "регулярные выражения" возникает потому, что они являются регулярной грамматикой, и изучение этих грамматик (часть теории вычислений) расскажет вам больше о том, какие именно задачи регулярные выражения могут решать, а какие - нет. Например, традиционный синтаксис регулярного выражения не сможет решить следующую проблему: проанализировать некоторое число N из символов "a" во входных данных, а затем проанализировать то же число N из символа "b".
Если вы заинтересованы в хорошем тексте об этом, ознакомьтесь с разделом Введение в теорию вычислений Майкла Сипсера. Хорошо.
Машина Тьюринга - это теоретическая вычислительная машина, изобретенная Аланом Тьюрингом в качестве идеализированной модели для математических вычислений, в основном это простая компьютерная форма, состоящая из ленты (бумажной ленты), с головкой, которая может читать символы, напишите новый символ на месте, а затем двигайтесь влево или вправо.
Говорят, что машина Тьюринга находится в определенном состоянии, а затем программа представляет собой список переходов, имеющих текущее состояние и символ под заголовком, что должно быть записано на ленте, какое будет следующее состояние и где голова должна двигаться.
Вот базовая машина Тьюринга, реализованная в JavaScript...
И набросок:
Мой IBM PC - это все, что мне нужно для вычислений!
Что-то, на что другие не указали: ваш IBM PC - машина Тьюринга. Точнее, это эквивалентно тому, что все, что может сделать ваш ПК, может сделать машина Тьюринга, и все, что может сделать машина Тьюринга, ваш ПК.
В частности, машина Тьюринга - это модель вычислений, которая полностью отражает понятие вычислимости, оставаясь при этом простой для размышлений, без каких-либо конкретных деталей архитектуры вашего ПК.
(Общепринятый) "тезис Черча-Тьюринга" утверждает, что каждое устройство или модель вычисления не более мощная, чем машина Тьюринга. Таким образом, многие теоретические проблемы (например, классы типа P и NP, понятие "алгоритм полиномиального времени" и т. Д.) Формально формулируются в терминах машины Тьюринга, хотя, конечно, они могут быть адаптированы к другим моделям как Что ж. (Например, иногда может быть удобно думать о вычислениях в терминах лямбда-исчисления, или комбинаторной логики, или чего-то еще... все они по мощности эквивалентны друг другу, а также вашему компьютеру IBM.)
Итак, вы идете: люди говорят о машинах Тьюринга, потому что это точный и полностью определенный способ сказать, что такое "компьютер", без необходимости описывать каждую деталь архитектуры ЦП, его ограничений и так далее.
Есть на самом деле примеры машин Тьюринга в природе. В частности, рибосома, которая переводит РНК в белки, реализует машину Тьюринга.
Сначала немного предыстории:
- РНК состоит из ряда нуклеотидов ("оснований"), которые определяют буквы генетического алфавита.
- В алфавите РНК есть 4 основания - A, C, G, U.
- Основы являются направленными: условно, концы называются пятью простыми и тремя простыми (5', 3')
- Основание в строке РНК может привлекать основание на другой строке РНК в "антипараллельных комплементарных парах", где А прилипает к U, а С - к G.
- Основания объединяются в группы по 3 человека, образуя "кодоны" (слова).
- Есть 64 возможных комбинации для кодонов (4^3).
- каждый кодон может соответствовать "анти-кодону". например, AUG <-> UAC
- Существуют специальные молекулы-носители ("тРНК"), которые имеют определенные антикодоны и прикреплены к определенным аминокислотам (белкам).
Операция рибосомы проста:
- транскрипция инициируется в "стартовом кодоне", который определяет "рамку считывания"
- транскрипция всегда идет в направлении 5'->3'
- кодон под рамкой считывания соответствует специфической тРНК, содержащей определенную аминокислоту
- стартовый кодон всегда кодирует аминокислоту метионин.
- новая аминокислота прикреплена к растущему белку
- кадр затем продвигает 3 основания к следующему кодону, и белок непрерывно расширяется
- при обнаружении "стоп-кодона" трансляция прекращается, аминокислота не присоединяется и рибосома диссоциирует от мРНК.
Как видите, это очень простая машина Тьюринга, которая выполняет самую сложную операцию - сама природа!
Машина Тьюринга - это теоретическая машина, которую можно использовать, чтобы рассуждать о границах компьютеров. Проще говоря, это воображаемый компьютер с бесконечной памятью.
Мы заботимся о машинах Тьюринга, потому что они помогают нам обнаружить, что невозможно сделать с реальными компьютерами (например, с вашим IBM PC). Если для машины Тьюринга невозможно выполнить какое-то конкретное вычисление (например, решить проблему остановки), то вполне понятно, что ваш IBM PC не может выполнить те же вычисления.
Почему люди, которые проектируют самолеты, заботятся о братьях Райт или о науке, стоящей за "подъемом", позволяющим летать самолетам с неподвижным крылом?
Алан Тьюринг считается отцом современных компьютеров. Машина Тьюринга является предшественником всех современных компьютеров.
Теория вычислимости была моим самым сложным занятием в колледже, но я рад, что взял его. Это заставило меня думать о вещах, которых я никогда не имел, или думать о вещах так, как я никогда бы не имел, и это хорошие вещи.
Машина Тьюринга - это абстрактная машина, способная к вычислениям.
Из Википедии:
Машины Тьюринга являются основными абстрактными символьными устройствами, которые, несмотря на свою простоту, могут быть адаптированы для моделирования логики любого компьютерного алгоритма. Они были описаны в 1936 году Аланом Тьюрингом. Машины Тьюринга предназначены не как практическая вычислительная технология, а как мысленный эксперимент о границах механических вычислений. Таким образом, они не были фактически построены. Изучение их абстрактных свойств дает много понимания компьютерных наук и теории сложности.
Машина Тьюринга, способная моделировать любую другую машину Тьюринга, называется универсальной машиной Тьюринга (UTM, или просто универсальной машиной). Более математически ориентированное определение с похожей "универсальной" природой было введено Алонзо Черчем, чьи работы по лямбда-исчислению переплетены с работами Тьюринга в формальной теории вычислений, известной как тезис Черча-Тьюринга. Тезис утверждает, что машины Тьюринга действительно отражают неформальное представление об эффективном методе в логике и математике и дают точное определение алгоритма или "механической процедуры".
Машина Тьюринга - это абстрактная машина, которая может работать с последовательностью данных и может изменять свое собственное состояние, а также данные во время работы, согласно некоторой логике.
Это концепция, которая лежит в основе алгоритмов, хранимых программ и вычислений в целом. Это обеспечивает хорошее понимание и абстракции, если вы имеете дело с алгоритмами, состояниями, данными и т. Д.
Пища для размышлений, для большинства.
В дополнение к записи в Википедии вы можете взять книгу Чарльза Петцольда "Аннотированная Тьюринг ". Подзаголовок "Экскурсия по исторической статье Алана Тьюринга о вычислимости и машине Тьюринга" включает в себя полный документ, разбитый на куски с множеством рассуждений на эту тему, включая историческую перспективу.
Машина Тьюринга эквивалентна алгоритму. Он останавливается, когда принимает строку, отклоняет или входит в бесконечный цикл, когда не принимает строку.
Лента действует как память, правила перехода действуют как условия "если тогда еще"
Самое удивительное в машине Тьюринга - это то, что это самая основная вычислительная машина из существующих, и она может выполнять вычисления столь же мощные, как и любой другой существующий сегодня компьютер. Нет никаких вычислительных проблем, которые вы можете решить на своем компьютере, которые вы не можете решить с помощью машины Тьюринга. Фактически, ваш компьютер - это TM, если вы хотите так смотреть на него.
Алан Тьюринг изобрел TM и использовал его определенную версию для декодирования нацистской шифровальной машины Enigma.
Итак, в заключение, это очень мощная машина, имеющая множество приложений в теоретической информатике. (Кстати, тоже очень интересная и стимулирующая тема).