1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

функциями над множеством всех чисел. Авфавип»ом называют непустое конечное множество символов. Например, Гт = (а, Ь), »сз = (О, Ц, Гз = (а, +, 1, =) — алфавиты. Словом в авфавип»е У называется конечный объект, получаемый выписыванием одного эа другим символов из У, например„ ааЬЬа — слово в алфавите Гт; 01О11 — слово в алфавите »"з; а + 1 = 1 + а — слово в алфавите Ез. Длина слова — число символов в нем, пустое елово не содержит ни одного символа. Множество всех азов в авфавик»е»' будем обозначать т'з.

Если а — символ, то а" — слово аа...а; множество (а"Ь" ) и) Ц— »» риз это множество слов (аЬ, ааЬЬ, аааЬЬЬ,...). и невки»ой словарной фуюцией на*д авфавитом У называют и-местную функцию над»'з, т. е. функцию из рчхуч х...хауз (и раэ) в Р". Пример всюду определенной двухместной словарной функции, которую называют комкал»ежщией: С (сз, р) = и(), где а Е= Гз, () б= Гз, а сз() — также слово иэ Г», полученное, приписыванием справа к слову и слова р. Слово у — псдслово слова,' »з, если а = руб; подслово у — префикс слова а, если () — пустое слово; подслово у — суффикс слова и, если 6 — пустое слово. Заметим, что существует взаимно однозначное соответствие между числами и словами в произвольном алфавите Г.

Действительно, символы из $' можно упорядочить, перенумеровав их числами 1, 2, ..., п, т. е. задав функцию упорядочения К: »с-»- -ь (1, 2,..., и). Пустому слову ставится в соответствие О. Слова упорядочиваются в последователъность по' следующему правилу: если длина слова сз меныпе длины слова р (оба из Гз), то а располагается левее р; слова одинаковой длины упорядочиваются в «алфавитном» порядке с учетом порядковых номеров символов алфавита, т. е. так же, как упорядочены слова в словарях естественных языков. Порядковый номер слова в полученной последовательности слов и задает соответствующее ему число (числовой код слова).

Обратное кодирование осуществляется тем же способом, т. е. с использованием некоторого упорядочения алфавита. Имея воэможность кодировать слова в произвольном алфавите числами, а числа — слонами в произвольном алфавите, можно осуществить взаимно однозначную кодировку слов в одном алфавите словами иэ другого алфавита. Зздзккв (Л.

А. Найти зкзлвтмчзсккй вкд фуккцмк, кодирующзй слова з злфззктз У = (а, Ь, с) числами, зслк фуккцкк упоркдочзмкк К: У ((, 2, 3) такова, тто К (в) = (, К (Ь) = 2, К (с) = 3. Б. Пусть Уз" — мкожеетзо всех наборов мз и слов з алфавите и. Покзжвтз, что между наборами кз У»" к чкслзмк существует взаимно одкозпзчкоз соотзетстзка. Закодировать числами пкрм слов з алфавите (а, Ь). 1.3. Вычислимые фукзции и мапшнь«Тьюринга.

Данное нами определение функции не содержит указаний о том, как для задан. нмх значений аргументов получить соответствующие значения функции. Было бы практичнее переформулировать зто определение таким образом, чтобы оно содержало конструктивную процедуру„ или алгоритм, нахождения значений функции. Однако, как будет видно далее, такое определение уже приведенного выше, т. е.

определяет лишь некоторый подкласс функций, которые называют вычислимыми функциями. В середине 30-х гг. Тьюринг (141(, Черч (91(, Клики 11131 н Пост (1321 различным образом формализовали способы получения значений вычислимых функций. Позднее было установлено, что все эти независимо введенные определения вычислимости, равно как и позднейшие формализации, например, нормальные алгоритмы Маркова (40(, эквивалентны, т.

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

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

Мажино Тьюринга Т задает словаркую функцию над некоторым алфавитом Г и представляет собой описание машины— набор (г', (~, %„~, 1) — и правило функционирования, общее для всех машин, где У вЂ” алфавит машины; (3 — конечное непустое множество символов, называемых еоеяязо»ил.ви машины (Д П У = Я); у — выделенный элемент множества 9, называемый начал нмм еоапоаниел«; ,~ — специальный «пустой» символ, не принадлежащий ни У, нк Е; 1 — нрагральио лялиинм. Программа машины — зто конечное множество слов вида оа о'а'«(, называемых командами, где д, о' ЕЕ (3, а,а' 6= Г Ц (Щ; -» — вспомогательный символ-разделитель; И вЂ” элемент множества (1, г, р1, содержшцего три специальных символа, которых нет ни в У, ни в (',1. Предполагается также, что в программе Х никакие две команды не могут иметь одинаковую пару первых двух символов.

Правило функционирования поясним неформально на распространенной «физической» модели машины Тьюринга. Машина 12 : состоит иэ потенциально бесконечной (в обе стороны) ленты, . управления и головки, перемещаемой вдоль ленты (рис. хЛ). Лента разбита на клетки, которые могут содержать символы из алфавита У или быть пустыни, т. е. содержать символ ~. Управление на каждом шаге работы машины находится в одном кэ состояний иэ (3, расшифровывает программу, которая однозначно определяет поведение машины и управляет головкой. Головка в каждый момент расположена против некоторой клетки ленты и может считывать символы с ленты, записывать их на ленту и перемещаться в обе стороны вдоль ленты. Машина функционирует следующим образом.

В начальный момент на ленте записано Головне Лента Рэс. 1Л. Машана Тьюрээгэ некоторое слово иэ У, а управление находится в качальном состоянии д. Начальное слово, равно как и слова, появляющиеся в процессе работы машины„ограничено с двух сторон пустыми символами '~.

Головка обозревает крайний слева символ заданного слова. Работа машины состоит в повторении следующего цикла элементарных действий". 1) считывание символа, находящегося против головки; 2) поиск применимой команды, а именно той команды да -+ -в- д'а'д, в которой о — текущее состояние управления, а — считанный символ; 3) выполнение найденной команды, состоящее в переводе управления в новое состояние д', записи в обоэреваемую головкой клетку символа а' (вместо стнраемого символа а) и последующем перемещении головки вправо, если д = г, влево, если И = 1, или сохранении ее в том же положении, если И =- р.

Машина останавливается в том и только в том случае, если ка очередном шаге ни одна иэ команд не применима. Результат работы остановившейся машины — заключительное слово на ленте. Машина Тьюринга, перерабатывая начальные слова на ленте в ваключнтельные, задает словарную функцию, для которой начал ыые слова — значения аргумента, заключительные — эна- 33 чения функции. (Для представления я-местной функции начальное слово на ленте имеет вид ~аг ~ аэ ф~... ф а ф~, где подслова а1, аз,..., а„не содержат символа ~.

При интерпретации заключительного слова на ленте как значения функции символ ~ игнорируется). Если машина не останавливается, начав работу с некоторым словом на ленте, то функция, задаваемая машиной, считается неопределенной для этого слова. Таким образом, машина Тьюринга Т задает частичную функцию Рг и способ вычисления ее значений. Хотя машины Тьюринга оперируют со словами, они могут задавать и числовые функции в силу установленной выше связи между словами н числами.

По определению, функция г" является (частично) вичислимой, если существует машина Тьюринга Т такая, что Рт = Р. Говорят также, что для функция Р существует (частичный) алзоритм вычисления ее значений, задаваемый машиной Т. В следующем параграфе мы убедимся в существовании функций, которые не являэггся вычкслимыми. Для машины Тьюринга, как и для всех других формальных способов задания алгоритмов, включая программы для ЭВМ„ характерны следующие свойства: 1) конструктивность — машина Тьюринга представляет собой конечный объект, построенный по определенным правилам иэ базовых объектов; 2) конечность — процесс нахождения значений функция длн тех значений аргументов, для которых она определена, состоит из конечного числа шагов; 3] однозначность — результат работы машины единственным образом определяется начальным словом; 4) массовость — машина работает с любым начальным словом на ленте, составленным иэ символов ее алфавита.

Характеристики

Список файлов книги