Определение минимального корня. Метод минимизации.
Операции примитивной рекурсии
Операция суперпозиции
Суть суперпозиции заключается в том, что вместо аргументов одних функций подставляются другие функции.
В общем виде:
Пусть заданы 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 Т – {Л,П,С}