Способы построения новых вычислимых функций

У нас имеется начальный набор простых (базовых)вычислимых функций. Мы будем пополнять этот наборвычислимых функций. Для этого разглядим способыпостроения из уже имеющихся вычислимых функций новых вычислимых функций. Оператор суперпозиции S. Разглядим действие,которое назовем оператором суперпозиции (постоянной суперпозиции). При помощи этого деяния из неких функций h, g1, g2,..., gm создается Способы построения новых вычислимых функций новенькая функция f. Пусть m, n – натуральные числа. Определим новейшую функцию f(x1,x2,...,xn) по правилу: f(x1,x2,...,xn)=h(g1(x1,x2,...,xn) ,g2(x1,x2,...,xn),...,gm(x1,x2,...,xn)).

Функция f является частичной функцией от n переменных. Ее значение f(x1,x2,...,xn) определено Способы построения новых вычислимых функций и тогда только тогда, когда определены все выражения в правой части из последнего равенства. Если функции h, g1,

g2,..., gmвычислимы, то и функция f вычислима. Метод ее вычисление

описывается правой частью равенства. В случае существования значения функции f, мы за конечное число шагов получим число f(x1,x2,...,xn) действиями Способы построения новых вычислимых функций, надлежащими интуитивному представлению об методе.

57) Определение примитивно-рекурсивной функции.Функция f именуется примитивно рекурсивной, если она может быть получена из простых функций следования, нулевой функции и функции проектирования при помощи конечного числа применений операторов суперпозиции и примитивной рекурсии. Тоже самое можно выразить в виде 3-х правил. 1) Простые функцииs(x Способы построения новых вычислимых функций)=x+1, on(x1,x2,...,xn)=0, In

m (x1,x2,...,xn)=xm примитивно рекурсивны. 2) Если функция f получена из примитивно рекурсивных функций при помощи оператора суперпозиции либо при помощи оператора примитивной рекурсии, то функция f примитивно рекурсивна. 3) То, что функция f примитивно рекурсивна, устанавливается несколькими применениями правил 1) и 2). Всякой примитивной рекурсивной функции Способы построения новых вычислимых функций можно приписать n -наименьший номер шага, на котором она может быть получена. Как следует, можно проводить подтверждение разных утверждений для примитивно рекурсивных функций индукцией по шагу, на котором они получены.

58) Примеры примитивно-рекурсивных функций.Аксиома 1. Последующие функции являются примитивно рекурсивными:

1. f(x)=x;

2. g(x)=x+2;

3. Неизменная унарная функция f Способы построения новых вычислимых функций(x)=a;

4. Нульарная функция.

Операция введения фиктивныхпеременныхПусть функция f(x1,x2,...,xn) примитивно рекурсивна. Добавим в строке

переменныхf(x1,x2,...,xn) еще одну переменную xn+1. Получим строчку x=(x1,x2,...,xn,xn+1) из n+1 переменной. Для функций проектирования явны n равенств In+1 (x)=x1,..., In+1n (x)=xn. Введем функцию f Способы построения новых вычислимых функций’(x) от n+1 переменной правилом f’ (x1,x2,...,xn,xn+1)=f(In+1 (x)=x1,..., In+1n (x))= f(x1,x2,...,xn). Потому что функция f примитивно рекурсивна, то и новенькая функция f’ примитивно рекурсивна. В предстоящем мы будем вводить фиктивную переменную, и из примитивно рекурсивной функции от n переменных получать Способы построения новых вычислимых функций примитивно рекурсивную функцию от n+1 переменной. При таковой операции введения фиктивного переменной заместо обозначения f’ для новейшей функции будем сохранять обозначение f начальной функции.Еще две примитивно рекурсивные функции Аксиома 2. Функция сложения f(x,y)=x+y и функция умножения f(x,y)=xy примитивно рекурсивны.

59) Частично-рекурсивные функции. Тезис Черча. Пусть Способы построения новых вычислимых функций дана вычислимая функция g(x1,x2,...,xn ,y) от n+1 переменной, где n0. Нам необходимо отыскать меньшее число y с условием g(x1,x2,...,xn ,y)=0. Введем последующее ограничение. Процедура нахождения числа y должна быть методом. Потому должен быть представлен четкий перечень действий для неинтеллектуального исполнителя Способы построения новых вычислимых функций (машины) по нахождению y,к примеру, поочередная проверка 1-го за другим последующих равенств

g(x1,x2,...,xn ,0)=0,

g(x1,x2,...,xn ,1)=0,

.............................

g(x1,x2,...,xn ,y)=0.

Что при всем этом произойдет? Может быть, вообщем нет числа y с условием g(x1,x2,...,xn ,y)=0. Тогда не произойдет остановки машины с выдачей y Способы построения новых вычислимых функций. Но отсутствие y может быть по другой причине. Представим, к примеру, что g(x1,x2,...,xn ,5)=0, , а значение g(x1,x2,...,xn ,2) не определено. Пытаясь вычислить g(x1,x2,...,xn,2) машина будет работать нескончаемо и никогда не перейдет к вычислению g(x1,x2,...,xn ,3). Потому число y=5 не Способы построения новых вычислимых функций будет найдено.

60)Оператор минимизации. Определение.Пусть g - функция от n+1 переменной. Будемговорить, что функция f от n переменных получена из функции g при помощи оператора минимизации,если равенство f(x1,x2,...,xn)=y правильно и тогда только тогда, когда g(x1,x2,...,xn, y) =0, а значения g(x Способы построения новых вычислимых функций1,x2,...,xn ,0), ... , g(x1,x2,...,xn ,y-1)определены и не равны нулю. Если функция f выходит из функции g при помощи оператора минимизации, то записываем f=M(g). Ясно, что аннотации для вычисления функции g и проверки выполнения процедуры минимизации образуют метод для вычисления значений функции f. Потому функция Способы построения новых вычислимых функций f вычислима.

61) Пример внедрения оператора минимизации.Пример. Отыскать функцию f, полученную из функции o(x) применением оператора минимизации. Решение. Если функция f получена из функции g при помощи оператора минимизации, то число ее переменных меньше числа переменных функции g на единицу. В этом случае g – это функция o(x Способы построения новых вычислимых функций) от одной переменной. Потому функция f имеет 0 переменных. Для нахождения значения функции f необходимо проверить условия o(0)=0, o(1)=0, ... , o(y)=0 и избрать в этих равенствах меньшее y. Так как o(x)=0 для всех x, то меньшее число y - это y=0. По определению оператора минимизации приобретенное y=0 и есть значение функции Способы построения новых вычислимых функций f. Потому функция f - это нульарная функция o0 со значением 0, т.е. помеченный элемент 0.

62) Машины Тьюринга Другой метод для обоснования понятия метода предложили независимо друг от друга и практически сразу с Черчем и Клини британский математик А. Тьюринг и южноамериканский математик Э. Пост. Основная мысль Поста и Тьюринга заключалась в Способы построения новых вычислимых функций том, что алгоритмические процессы – это процессы, которые может совершать некая «машина». Машины, введенные Постом и Тьюрингом, имеют не очень большое отличие и обычно именуются машинами Тьюринга.

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

Любая ячейка содержит ровно один из знаков 0 либо 1. Лента представляется конечной, но дополняемой в хоть какой момент ячейками слева и справа для записи новых знаков 0 либо 1. Эта ситуация может появиться при сдвиге каретки на лево либо на право за Способы построения новых вычислимых функций край ленты. Тогда нарастает новенькая клеточка с содержимым 0. Это соглашение отражает идею о сколь угодно большой, но конечной памяти. Если каретка, размещена над некой ячейкой с эмблемой 0 (с эмблемой 1), то говорим, что каретка обозревает знак 0 (обозревает знак 1).

64) Программки машины Тьюринга.Машина Тьюринга имеет программку. Это конечная последовательность инструкций q Способы построения новых вычислимых функций1, q2, ... ,qn, любая из которых является строчкой из компонент: (i, a, x, y, z ), где i – номер аннотации;

a =0, либо a=1;

x=0, либо x=1;

у= L либо y=R;

z – номер аннотации.

65) Вычисление значений функций.Разглядим метод вычисления значений функций на машине Тьюринга. Поначалу договоримся о представлении натуральных чисел Способы построения новых вычислимых функций на ленте: 1) натуральное число 0 будем изображать одной единицей, число 1 – 2-мя единицами, и т. д., натуральное число x – (x+1) - ой единицей:

2) Для изображения упорядоченной последовательности (x1, x2, ... , xn) будем каждую группу единиц отделять друг от друга нулем. Пример. Так смотрится на ленте тройка чисел (3, 1, 10):

1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1

Пусть дана n-арная функция f Способы построения новых вычислимых функций(x1,x2, ... , xn). Будем гласить, что машина Тьюринга M вычисляет функцию f, если производятся последующие условия.

1. Пусть строчка (x1,x2, ... , xn) содержится в области определения функции f. Тогда машина M, начиная работать и обозревая левую единицу строчки (x1,x2, ... ,xn) (остальная часть ленты пуста), на неком шаге останавливается, обозревая Способы построения новых вычислимых функций левую единицу строчки f(x1,x2, ... , xn) (часть ленты справа от строчки пуста). 2. Пусть строчка (x1,x2, ... , xn) не содержится в области

определения функции f. Тогда машина M работает

нескончаемо.

65) Пример вычисление функции на машине Тьюринга.Построим машину Тьюринга, вычисляющую значения функции f(x,y)=x+y. Пусть на ленте находятся два Способы построения новых вычислимых функций числа x и y. Разумеется, что складывая эти числа мы должны убрать меж ними 0 и уменьшить число единиц на два. В итоге на ленте должно остаться (x+y+1) единиц, идущих поочередно вереницей. Поначалу проходим через x:(0, 1, 1, R,0). Эта аннотация повторится ровно x раз. Потом каретка окажется над Способы построения новых вычислимых функций нулем,разделяющим числа x и y. Этот ноль заменяем единицей при помощи аннотации: (0, 0, 1, R, 1). Сейчас проходим через число y:(1, 1, 1, R, 1). Доходим до конца числа y. Каретка опять оказалась над нулем. Возвращаемся на одну ячейку вспять и стираем одну, а потом еще одну единицу: (1, 0, 0, L,2), (2, 1, 0, L,3),(3, 1, 0, L,4). После стирания 2-ух единиц можно возвратиться Способы построения новых вычислимых функций вспять и тормознуть: (4, 1, 1, L, 4), (4, 0, 0, R,5).

67) Тезис Тьюринга.Сейчас мы располагаем всеми необходимыми определениями для четкой формулировки понятия метода. Из определения машины Тьюринга легкоубедиться, что ее работа удовлетворяет всем требованиям, предъявляемым кпонятию метода. Потому случайная функция, вычислимая на машинеТьюринга, является вычислимой функцией. Разглядим воззвание этогоутверждения. Тезис Тьюринга. Если Способы построения новых вычислимых функций функция f является вычислимой, то существует машина Тьюринга вычисляющая функцию f. Сможем ли мы обосновать тезис Тьюринга? Нет, т.к. у нас нет четкого определения понятия вычислимой функции. Тезис Тьюринга является результатом, возникшимиз опыта. Тезис Тьюринга - очередной вариант определения метода, так как отождествляет интуитивное понятие вычислимой функции со серьезным Способы построения новых вычислимых функций понятием функции, вычислимой на машине Тьюринга. Подтверждена равносильность тезиса Тьюринга и тезиса Черча. Это подкрепляет уверенность в том, что оба тезиса правильно отражают понятие метода. Тезисы Тьюринга и Черча можно рассматривать как теоретические границы способностей реальных вычислительных машин.

68) Конфигурация машиныМашинным словом, либо конфигурацией машины M, именуется слово вида AqkalB, где Способы построения новых вычислимых функций A и B - слова в алфавите A. Так изображается содержимое ленты и обозреваемая ячейка. При всем этом считаем, что машина находится в состоянии qk , а каретка обозревает на ленте знак al . Слова A и B отражают содержимое ленты до и после знака al . Группу из x знаков a на ленте Способы построения новых вычислимых функций будем обозначать через ax.

69) Применение машины Тьюринга к словамЗадачка 1. Имеется машинаТьюринга с внешнималфавитом A={a0, 1} с алфавитом внутренних состояний Q={q0, q1} ипрограммой, представленной в таблице. Найти в какие словаперерабатывает программка каждое из следующихслов:

1) 1 a0 11 a0 a0 11 (4 ячейка) 2) 1 a0 111 a0 a0 11 (2 ячейка) 3) 1 a0 a0 111 (3 ячейка)

70) Машины с неограниченными регистрами Способы построения новых вычислимых функций.Машина с неограниченными регистрами (МНР) – это абстрактная машина, более

схожая с реальным компом по сопоставлению с машиной Тьюринга. Она имеет последующие составные части. 1) Регистры R1, R2, ..., в каких содержатся соответственно натуральные числа r1, r2, ... . Число регистров нескончаемо, но только конечное огромное количество регистров R1, R2, ... Rk содержит Способы построения новых вычислимых функций числа, хорошие от нуля. Все другие регистры заполнены нулями.

Программка машины – это конечная последовательность I1, I2, ... , Is. Из последующих 4 типов команд:

Z(n), S(n), T(m, n), J(m, n, q), где m, n, q \{1,2, ... }. Эти команды делают последующие деяния. Команда обнуленияZ(n) делает содержимое регистра Rn равным нулю Способы построения новых вычислимых функций. Команда добавления единицы S(n) к содержимому регистра Rn добавляет число1. Команда переадресацииT(m, n) подменяет содержимое регистра Rn на содержимое регистра Rm. Команда условного перехода J(m, n, q) ассоциирует содержимое регистров Rm и Rn. При rm = rn в качестве последующей команды производится команда с номером q, в неприятном Способы построения новых вычислимых функций случае производится последующая по порядку команда программки.

Команды обнуления, добавления единицы и переадресации именуются

арифметическими командами.


sposobi-zadaniya-tochek-2-h-mernih-sposobi-obespecheniya-tochnosti.html
sposobi-zaklyucheniya-i-prekrasheniya-braka.html
sposobi-zapisi-algoritmov.html