Работа - машина - тьюринг
Cтраница 2
Но согласно лемме 6, этот вопрос можно решить за 2c ( i) iog ( / i i) шагов работы машины Тьюринга. [16]
Голсвка стоит над первой слева единицей. В результате работы машины Тьюринга это слово превращается в НПО. По окончании работы машины головка стоит над крайней правой единицей. [17]
Эти пятерки называются командами. Список всех пятерок, определяющих работу машины Тьюринга, называется программой этой машины. [18]
Однако, рассмотренный нами общий способ интерпретации работы машин Тьюринга сам является алгоритмом, а стало быть и ему должна соответствовать некоторая машина Тьюринга, в которой входное слово состоит из изображения программы и входного слова интерпретируемой машины. Такая машина называется универсальной, так как она способна выполнять задания для любой машины Тьюринга. Мы не будем описывать здесь программу универсальной машины Тьюринга, а рассмотрим только, как можно представлять информацию на ее ленте. [19]
Наблюдение, что несколько различных определений того, что значит для функции быть вычислимой, приводит к одному и тому же множеству вычислимых функций, это ведет к основному тезису Черча, согласно которому все вычислительные устройства могут быть смоделированы на машине Тьюринга. Этот тезис сильно упрощает изучение вычислительных процедур, так как сводит поле возможных исследований, состоящее из бесконечного числа потенциально возможных вычислительных устройств, к изучению работы машин Тьюринга. Тезис Черча не является математической теоремой, для того чтобы сделать его теоремой, нам бы понадобилось знать точное математическое описание таких вычислительных устройств. Такое описание, однако, всегда оставляет возможным создание некоего реального вычислительного устройства, которое не удовлетворяет такому точному математическому описанию, и, таким образом, окончательная математическая теорема должна быть более слабой, чем оригинальный тезис Черча. [20]
Чтобы с уверенностью констатировать эту возможную разницу, необходимо будет использовать некоторые волшебные свойства квантовой механики - мистической, но все же поразительно точной теории, описывающей поведение атомов и молекул, а также и другие явления, многие из которых представляют интерес и на макромасштабах. Пока совершенно неясно, как на практике сконструировать такое физическое устройство, которое бы ( надежно) функционировало по принципу квантового компьютера - и, более того, рассматриваемый до сих пор класс задач носил заведомо искусственный характер, - но теоретически понятно, что квантовое физическое устройство могло бы улучшить работу машины Тьюринга. [21]
Таким образом, если задана начальная конфигурация машины, состоящая из считанного символа и состояния автомата, то по таблице можно определить, в какую конфигурацию перейдет машина на следующем такте работы. Некоторые состояния можно объявить заключительными и считать, что работа машины заканчивается, как только она попадает в одно из таких состояний. Работа машины Тьюринга в конечном итоге заключается в преобразовании некоторого текста, записанного на ленте, в некоторый другой текст, который остается на ленте после работы машины. Алгоритмы такого преобразования задается таблицей, о которой шла речь выше. Тьюринг предложил алгоритмом называть то, что может быть задано в виде действий описанного выше автомата и высказал тезис о том, что любой алгоритм символьных преобразований, любой вычислительный алгоритм, если он существует, может быть представлен соответствующей машиной. [22]
 |
Многоленточная машина Тьюринга. [23] |
Каждая лента разбита на клетки, каждая из которых содержит один из конечного числа символов на ленте. Одна клетка на каждой ленте обозревается головкой этой ленты; головка может считывать с ленты и записывать на нее. Работа машины Тьюринга определяется простой программой, называемой управляющим устройством. Оно всегда находится в одном из конечного числа состояний, которое можно рассматривать как номер текущей команды в программе. [24]
О ячейке, в которой записан пустой символ, будем говорить, что она пустая. Если все ячейки ленты пустые, то и сама лента пустая. К началу работы машины Тьюринга на ленте записана начальная информация, которая состоит из конечного числа непустых ячеек. В дальнейшем будет видно, что в процессе работы машины на ленте каждый раз имеется конечное число непустых ячеек. [25]
Понятие нормальной модели вычислений обобщает как нормальные алгоритмы, так и машины Тьюринга. Подробно об этих понятиях см., например, [ Sa ], Гл. В широком смысле, р 6 Р - список подстановок алгоритма Маркова или таблица, определяющая работу машины Тьюринга. Тогда миры С /, /, F состоят из разных слов в рабочем алфавите. [26]
Таким образом, машины Тьюринга - это тексты на некотором языке, а вовсе не машины в обычном смысле слова. Эти тексты имеют естественный смысл, присущий им как текстам естественного языка, смысл описаний некоторых устройств и выполняемых ими действий. Но они имеют и второй смысл - математический, определяющий действия человека, якобы наблюдающего за работой машины Тьюринга, а в действительности выполняющего определяемый ее конструкцией процесс. При этом основной частью, определяющей действия исполнителя, следует считать функциональную таблицу, так как именно она определяет конкретный процесс преобразования исходного данного. Таким образом, машина Тьюринга представляет собой алгоритм, записью которого можно считать функциональную таблицу, а правилом ( алгоритмом) выполнения - описание ее устройства. Приведенный выше пример показывает, что, в частности, можно строить машины Тьюринга для вычисления рекурсивных функций. [27]
Большинство современных языков программирования относятся к этому классу, поэтому такой метод контроля для них является полным. Однако если в САП будет применен какой-либо новый язык программирования или введено расширение старого языка, выводящее его из класса языков, порождаемых грамматикой предшествования, то такой метод контроля также окажется неполным. Так, контекстно-свободные языки, задаваемые правилами Бэкуса, для своего полного синтаксического контроля требуют более широкого метода, основанного на применении принципов, совпадающих с принципами работы машин Тьюринга с магазинной памятью. Этот принцип учитывает метаре-зультат, для которого производится анализ очередного символа. [28]
Машины Тьюринга не только соответствуют некоторым алгоритмам специального вида, но и сами являются ими. Действительно, читатель уже понял, что машины Тьюринга - это воображаемые машины, существующие не физически, а идеально, в наших мыслях, а точнее - в виде некоторых текстов на естественном языке. Сконструировать машину Тьюринга - значит составить ее описание, а не изготовить техническое устройство. Работа машины Тьюринга заключается в том, что человек выполняет определенные действия, руководствуясь описанием машины Тьюринга и ее функциональной таблицей, имея заданное начальное ( подлежащее преобразованию) слово и получая на очередном шаге промежуточный результат. [29]
Несмотря на свое простое устройство, машина Тьюринга может выполнять самые сложные преобразования слов. Сначала, когда лента содержит входное слово, автомат находится против какой-то ячейки и в каком-то состоянии. Необходимо договориться, какая это будет ячейка: например, самая левая непустая, третья от конца слова или какая-нибудь еще. В зависимости от выбора начальной ячейки, получатся разные результаты работы машины Тьюринга. [30]
Страницы: 1 2 3