Что такое машина Тьюринга?
https://stackoverflow.com/questions/236000
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Что такое машина Тьюринга и почему люди продолжают ее упоминать? Мой IBM PC - это все, что мне нужно для вычислений! Почему кто-то заботится об этих машинах?
Решение
Причина, по которой машины Тьюринга имеют большое значение, связана с изучением классических вещей типа Computing Science или Theory of Computation. В основном речь идет об анализе общих свойств компьютера, таких как те теоретические возможности и ограничения, которые есть у компьютера, а также то, что мы имеем в виду, когда говорим о & Quot; computing & Quot; что-то.
Одним из примеров того, что можно изучить с помощью машин Тьюринга, является Проблема остановки . Хотя эта проблема является чем-то вроде академического упражнения, она имеет вполне ощутимые практические последствия. Почему бы не написать отладчик, который просто скажет вам, содержит ли ваша программа бесконечные циклы? Проблема Остановки устанавливает, что решение этой проблемы для общего случая невозможно.
Изучение машин Тьюринга также позволяет изучать языковые грамматики и их классы, что приводит к разработке языка программирования. Термин & Quot; регулярные выражения & Quot; происходит потому, что они представляют собой обычную грамматику и изучение этих грамматик (часть теории вычислений) ) расскажет вам больше о том, какие именно проблемы могут решать регулярные выражения, а какие нет. Например, традиционный синтаксис регулярного выражения не сможет решить следующую проблему: проанализировать некоторое число N из символов 'a' во входных данных, а затем проанализировать то же число N из символа char 'b'.
Если вас интересует хороший текст об этом, ознакомьтесь с введением к теории вычислений Майкла Сипсера. Это хорошо.
Другие советы
Машина Тьюринга - это теоретическая вычислительная машина, изобретенная Аланом Тьюрингом в качестве идеализированной модели для математических вычислений, в основном это простая компьютерная форма, состоящая из ленты (бумажной ленты). ), имеет head , который может читать символы, писать новый символ на месте, а затем перемещаться влево или вправо.
Говорят, что машина Тьюринга находится в определенном состоянии , а затем программа представляет собой список переходов , имеющий текущее состояние и символ под заголовком, что должно быть написано на ленте, какое будет следующее состояние и куда должна двигаться голова.
Вот Базовая машина Тьюринга , реализованная в JavaScript ...
И эскиз:
Мой IBM PC - это все, что мне нужно для вычислений!
Что-то, на что другие не указали: ваш IBM PC является машиной Тьюринга. Точнее, он эквивалентен этому в том смысле, что все, что может сделать ваш ПК, может сделать машина Тьюринга, и все, что может сделать машина Тьюринга, ваш ПК.
В частности, машина Тьюринга - это модель вычислений , которая полностью отражает понятие вычислимости, оставаясь при этом простой для рассуждения без каких-либо конкретных деталей архитектуры вашего ПК.
(Общепринятый) & тезис Церковного Тьюринга " утверждает, что каждое устройство или модель вычислений не более мощная, чем машина Тьюринга. Таким образом, многие теоретические проблемы (например, классы типа P и NP, понятие & Quot; алгоритм полиномиального времени & Quot; и т. Д.) Формально формулируются в терминах машины Тьюринга, хотя, конечно, их можно адаптировать и к другим моделям. (Например, иногда может быть удобно думать о вычислениях в терминах лямбда-исчисления, или комбинаторной логики, или чего-либо еще ... все они равны по мощности друг с другом, а также с вашим компьютером IBM.)
Итак, вы идете: люди говорят о машинах Тьюринга, потому что это точный и полный конкретный способ сказать, что такое " computer " без описания всех деталей архитектуры ЦП, его ограничений и т. д.
В природе есть примеры машин Тьюринга. В частности, рибосома , которая переводит РНК в белки, реализует машину Тьюринга.
Сначала немного истории.
<Ол>Операция с рибосомой проста:
<Ол>Как видите, это очень простая машина Тьюринга, которая выполняет самую сложную операцию - сама природа!
Машина Тьюринга - это теоретическая машина, которую можно использовать, чтобы рассуждать о границах компьютеров. Проще говоря, это воображаемый компьютер с бесконечной памятью.
Мы заботимся о машинах Тьюринга, потому что они помогают нам обнаружить то, что невозможно сделать с реальными компьютерами (например, с вашим IBM PC). Если для машины Тьюринга невозможно выполнить конкретное вычисление (например, решить проблему остановки ), тогда понятно, что ваш IBM PC не может выполнить те же вычисления.
Почему люди, которые проектируют самолеты, заботятся о братьях Райт или о науке, стоящей за & "поднять"! " что позволяет самолетам с фиксированным крылом летать?
Алан Тьюринг считается отцом современных компьютеров. Машина Тьюринга является предшественником всех современных компьютеров.
Теория вычислимости была моим самым сложным занятием в колледже, но я рад, что взял его. Это заставило меня задуматься о вещах, которых у меня никогда не было, или думать о вещах так, как никогда раньше, и это хорошие вещи.
Машина Тьюринга - это абстрактная машина, способная к вычислениям.
Из Википедии
Машины Тьюринга - это основные абстрактные устройства для работы с символами, которые, несмотря на свою простоту, могут быть адаптированы для имитации логики любого компьютерного алгоритма. Они были описаны в 1936 году Аланом Тьюрингом. Машины Тьюринга предназначены не как практическая вычислительная технология, а как мысленный эксперимент о границах механических вычислений. Таким образом, они не были фактически построены. Изучение их абстрактных свойств дает много понимания компьютерных наук и теории сложности.
Машина Тьюринга, способная моделировать любую другую машину Тьюринга, называется универсальной машиной Тьюринга (UTM, или просто универсальной машиной). Более математически ориентированное определение с похожим & Quot; универсальным & Quot; Природа была введена Алонзо Черчем, чьи работы по лямбда-исчислению переплетены с работами Тьюринга в формальной теории вычислений, известной как тезис Черча-Тьюринга. Тезис утверждает, что машины Тьюринга действительно отражают неформальное понятие эффективного метода в логике и математике и дают точное определение алгоритма или «механической процедуры».
Машина Тьюринга - это абстрактная машина, которая может работать с последовательностью данных и может изменять свое собственное состояние, а также данные во время работы, в соответствии с некоторой логикой.
Это концепция, которая лежит в основе алгоритмов, хранимых программ и вычислений в целом. Он обеспечивает хорошее понимание и абстракции, если вы имеете дело с алгоритмами, состояниями, данными и т. Д.
Пища для размышлений, для большинства.
В дополнение к записи в Википедии вы можете захотеть забрать книгу Аннотированный Тьюринг Чарльза Петцольда. & Подзаголовок «Экскурсия по исторической статье Алана Тьюринга о вычислимости и машине Тьюринга &», Включающая полную статью, разбитую на куски с множеством рассуждений на эту тему, включая историческую перспективу.
Машина Тьюринга эквивалентна алгоритму. Он останавливается, когда принимает строку, отклоняет или входит в бесконечный цикл, когда не принимает строку.
Лента действует как память, правила перехода действуют как условия «если тогда еще»
