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

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

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

Для некоторого заданного набора значений x₁ = a₁, x₂ = a₂,…, x_n = a_n в качестве значения функции f(x₁,…,x_n) = y принимается наименьший целый неотрицательный корень уравнения g(a₁,…,a_n,y) = 0.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

S_i

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

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

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

Состояния:

Ø Л – лево;

Ø П – право;

Ø С – стоп.

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

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

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

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

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

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

g_iS_i → g_jS_jK

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

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

Q	a	b	c
q0	gjSjK
q1
…
qn

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

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

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

q_iS_i→q_jS_jK S₁S₂S₃q_jS_4…S_n

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

q_i0→q_jaT a – 0 или 1

q_i1→q_j1T Т – {Л,П,С}