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

Question

Что такое машина Тьюринга и почему люди продолжают упоминать ее? Мой IBM PC - это все, что мне нужно для вычислений! Почему кто-то заботится об этих машинах?

Answer 1

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

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

Изучение машин Тьюринга также позволяет изучать языковые грамматики и их классы, что приводит к разработке языка программирования. Термин «регулярные выражения» появился потому, что они являются регулярной грамматикой , и изучение этих грамматик (часть теории вычислений) расскажет вам больше о том, какие именно проблемы могут решать регулярные выражения и какие они не могут Например, традиционный синтаксис регулярного выражения не сможет решить следующую проблему: проанализировать некоторое число N из символов 'a' во входных данных, а затем проанализировать то же число N из символа char 'b'.

Если вам интересен хороший текст о подобных вещах, ознакомьтесь с Введение в теорию вычислений , автором которого является Майкл Сипсер. Это хорошо.

Answer 2

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

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

Вот базовая машина Тьюринга , реализованная в JavaScript ...

И эскиз:

Answer 3

Мой компьютер IBM IBM - это все, что мне нужно для вычислений!

То, на что другие не указали: ваш IBM PC - это машина Тьюринга. Точнее, он эквивалентен этому в том смысле, что все, что может сделать ваш ПК, может сделать машина Тьюринга, и все, что может сделать машина Тьюринга, может сделать ваш компьютер.

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

(Общепринятый) «тезис Черча-Тьюринга» утверждает, что каждое устройство или модель вычисления не более мощная, чем машина Тьюринга. Итак, многие теоретические проблемы (например, классы типа P и NP, понятие «алгоритм полиномиального времени» и т. Д.) Формально формулируются в терминах машины Тьюринга, хотя, конечно, они могут быть адаптированы к другим моделям как Что ж. (Например, иногда может быть удобно думать о вычислениях в терминах лямбда-исчисления, или комбинаторной логики, или чего-либо еще ... все они эквивалентны по мощности друг другу, а также вашему компьютеру IBM.)

Итак, вы идете: люди говорят о машинах Тьюринга, потому что это точный и полный конкретный способ сказать, что такое «компьютер», без необходимости описывать каждую деталь архитектуры ЦП, его ограничений и т. Д.

Answer 4

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

Сначала немного фона:

1. РНК состоит из строки нуклеотиды («основания»), которые определяют буквы генетического алфавита.
2. В РНК 4 основания алфавит - A, C, G, U.
3. Основы являются направленными: Конвенция, концы называются пять простых и три простых (5 ', 3')
4. Основание в строке РНК может привлекать основание на другой строке РНК в «антипараллельном комплементарном» пары ", где A прилипает к U, а C - к G.
5. Основания объединены в группы 3, чтобы сформировать «кодоны» (слова).
6. Есть 64 возможных комбинации для кодонов (4 ^ 3).
7. каждый кодон может соответствовать «анти-кодону». например AUG <-> UAC
8. есть специальные молекулы-носители («тРНК»), которые имеют особые антикодоны и прикреплены к специфические аминокислоты (белки).

Операция рибосомы проста:

1. транскрипция начинается при «старте» кодон ", который определяет" чтение кадр "
2. транскрипция всегда выполняется в направлении 5 '-> 3'
3. кодон под рамкой считывания сопоставляется с конкретной тРНК содержащий специфическую аминокислоту
4. стартовый кодон всегда кодирует аминокислота метионин.
5. новая аминокислота прикреплена к растущему белку
6. кадр затем продвигает 3 основания к следующему кодону, и белок непрерывно расширяется
7. при обнаружении «стоп-кодона» трансляция прекращается, аминокислота не присоединяется и рибосома диссоциирует от мРНК.

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

Answer 5

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

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

Answer 6

Почему люди, которые проектируют самолеты, заботятся о братьях Райт или науке о «подъемной силе», позволяющей летать самолетам с неподвижным крылом?

Алан Тьюринг считается отцом современной вычислительной техники. Машина Тьюринга является предшественником всех современных компьютеров.

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

Answer 7

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

Это концепция, которая лежит в основе алгоритмов, хранимых программ и вычислений в целом. Он обеспечивает хорошее понимание и абстракции, если вы имеете дело с алгоритмами, состояниями, данными и т. Д.

Пища для размышлений, для большинства.

Answer 8

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

Из Википедии:

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

Машина Тьюринга, способная моделировать любую другую машину Тьюринга, называется универсальной машиной Тьюринга (UTM, или просто универсальной машиной). Более математически ориентированное определение с аналогичной «универсальной» природой было введено Алонзо Черчем, чьи работы по лямбда-исчислению переплетены с работами Тьюринга в формальной теории вычислений, известной как тезис Черча-Тьюринга. Тезис утверждает, что машины Тьюринга действительно отражают неформальное понятие эффективного метода в логике и математике и дают точное определение алгоритма или «механической процедуры».

Answer 9

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

Лента действует как память, правила перехода действуют как условия «если тогда еще»

Answer 10

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