Определение минимального корня. Метод минимизации.

Операции примитивной рекурсии

Операция суперпозиции

 

Суть суперпозиции заключается в том, что вместо аргументов одних функций подставляются другие функции.

В общем виде:

Пусть заданы n-функций f1,f2,…,fn от m аргументов каждая и некоторая функция f(x1,x2,…,xn) f(a1,a2,…,am), тогда операция суперпозиции означает, что можем получить новую функцию g(x1,…,xm) = f(f1(…), f2(...),…,fn(…))

 

Пример:

1. Даны две функции f(x)=0; g(x)=x+1

h(x) = g(f(x)) = 0+1 = 1

H(x) = g(g(x)) = x+2

 

2. Даны две функции f(x)=0; g(x)=x

h(x) = g(f(x)) = 0

H(x) = g(g(x)) = x

 

3. Даны две функции f(x)=x; g(x)=x+1

h(x) = g(f(x)) = x+1

 

В результате при операции суперпозиции получаются 2 новые функции при f(x)=0 и g(x)=x+1, в других случаях функция не изменяется.

 

 

Операция примитивной рекурсии позволяет строить n+1 одноместную функцию по двум заданным функциям, одна – n - местная, вторая – n+2-местная. f от n+1

g от n

h от n+2

Пусть заданы частичные арифметические функции g(x1,…,xn) и h(x1,…,xn,xn+1, xn+2). Тогда функция f получается из g и h с помощью применения рекурсии:

f(x1,x2,…xn,0) = g(x1,x2,…xn)

f(x1,x2,…xn,y+1) = h (x1,x2,…xn,y, f(x1,x2,…xn,y))

Любая функция с меньшим количеством аргументов может быть получена из функции с большим количеством аргументов.

На основе данного определения можно определить функцию константу.

f(0) = a

f(x+1) = h(x0,f(x))

Если функции g и h существуют, то необходимо установить существует ли функция f получаемая примитивной рекурсией и будет ли она единственная.

f(x1,…,xn,0) = g(x1,…,xn)

f(x1,…,xn,1) = h(x1,…,xn,0,g(x1,…,xn))

f(x1,…,xn,2) = h(x1,…,xn,1,h(x1,…,xn,1))

…………………………………………..

f(x1,…,xn,m+1) = h(x1,…,xn,m,f(x1,…,xn,m))

 

Вычислим любые значения этой функции

f = x+y

g(x) = x – функция повторения

h(x,y,z) = z+1 – функция следования

f(x,0) = x

f(x,1) = h(x,0,x) = x+1

f(x,2) = h(x,1,x+1) = x+2

 

Двухместную функцию x*y можно вычислить, используя функции

f = xy

g(x) = 0

h(x,y,z) = z+x

 

В теории алгоритмов есть операция вычитания:

f = x y =

 

 

С помощью операции минимизации определяется новая арифметическая функция f(n) с помощью ранее построенной арифметической функции g(n+1).

Это реализуется следующим методом.

Для некоторого заданного набора значений x1 = a1, x2 = a2,…, xn = an в качестве значения функции f(x1,…,xn) = y принимается наименьший целый неотрицательный корень уравнения g(a1,…,an,y) = 0.

Таким образом, механизм вычисления функции f сводится к тому, что фиксируется набор аргументов и затем решается уравнения.

Данный процесс будет продолжаться бесконечно в следующих случаях:

Ø если значения f(x1,…,xn, xn-1, 0) в точке 0 для xn не определено;

Ø f(x1,…,xn-1, y) для y = 1,2,3,…,a-1) в точке y = a значение функции не определено.

 

Машины Тьюринга (МТ)

МТ также относится к алгебраическим системам.

МТ представляет собой совокупность трех элементов:

1. бесконечная лента, разделенная на ячейки, в каждой из которых записывается один символ входного алфавита;

2. считывающая головка, которая в каждый момент времени находится над какой-то ячейкой ленты;

3. управляющее устройство, которое выполняет некоторый фиксированный набор команд:

Ø читать символ, находящийся в ячейке под считывающей головкой;

Ø записать в ячейку новый символ;

Ø переместить ленту влево на одну ячейку;

Ø переместить ленту вправо на одну ячейку;

Ø остаться в этой же позиции.

 

         

Si

В результате МТ может выполнить следующие команды:

Ø считать Si символ и в зависимости от этого символа перемещать ленту влево, вправо либо остаться на месте;

Ø читать символ Si и в зависимости от его значения заменить его новым символом.

 

Состояния:

Ø Л – лево;

Ø П – право;

Ø С – стоп.

МТ задается следующим набором данных:

– входной алфавит;

Q – внутренний алфавит, множество состояний;

H – множество команд которые МТ может реализовать.

Множество команд H можно задавать двумя способами:

1. Перечень строк каждая, из которых состоит из 5 символов;

giSi → gjSjK

Находясь в состоянии gi над ячейкой Si переходит в состояние gj заменяя символ на Sj, завершает действие К = (Л,П,С). При этом Sj может быть равен Si.

2. Множество команд H задается таблицей:

 

  Q   a   b   c
q0 gjSjK    
q1      
     
qn      

 

Необходимо указать конечное состояние. Если символа в ячейке нет то это S0. МТ останавливается в двух случаях: когда находясь в некотором состоянии не находится команды из множества Н и когда попадает в конечное состояние.

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

 

Команда Конфигурация

qiSi→qjSjK S1S2S3qjS4…Sn

 

Стандартная МТ с внешним алфавитом {0,1} называется не стирающей, если она способна выполнять только команды:

qi0→qjaT a – 0 или 1

qi1→qj1T Т – {Л,П,С}