Какая машина Тьюринга?

Ответ 1

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

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

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

Если вам интересен хороший текст об этом, посмотрите Введение в теорию вычислений Michael Sipser. Это хорошо.

Ответ 2

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

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

Вот Basic Turing Machine, реализованный в JavaScript...

И эскиз:

машина turing http://weblog.fortnow.com/media/turing-machine.jpg

Ответ 3

Мой IBM PC - это все, что мне нужно для выполнения моих вычислений!

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

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

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

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

Ответ 4

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

Во-первых, некоторый фон:

• РНК состоит из строки нуклеотиды ( "основания" ), которые определяют буквы генетического алфавита.
• В РНК есть 4 базы алфавит - A, C, G, U.
• Базы являются направленными: по соглашение концы называются пять-премьер и три -прим (5 ', 3')
• База в строке РНК может привлечь базу на другую строку РНК в "антипараллельном дополняющем пары ", где A прилипает к U и C к G.
• Основания объединяются в группы 3 для формирования "кодонов" (слов).
• Существует 64 возможных сочетания для кодонов (4 ^ 3).
• каждый кодон может соответствовать "антикодону". например AUG ↔ UAC
• существуют специальные молекулы-носители ( "тРНК" ), которые имеют антикодонов и прикреплены к специфические аминокислоты (белки).

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

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

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

Ответ 5

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

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

Ответ 6

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

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

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

Ответ 7

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

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

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

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

Ответ 8

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

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

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

Ответ 9

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

Ответ 10

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

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