Композиция машин

Композицией машин Т₁ и Т₂ называется машина Т₁○Т₂ с внешним алфавитом А₁ А₂, алфавитом состояний {Q₁ Q₂\q₀}, q₀ – заключительноесостояние Т₁ и работающая по правилу:

(Т₂○Т₁) (И) = Т₂(Т₁(И))

Пример.

Пусть даны две машины:

Т₁: А₁={ |, +, } Q₁ = {q₀, q₁, q₂, q₃}

Т₂: А₂={ |, α, } Q₂ = {q₀, q₁, q₂, q₃}

Тогда

Т₂○Т₁: А₁ А₂ = ={ |, +, , α }; Q₁ Q₂ = {q₀, q₁, q₂, q₃}

Т₂○Т₁ (И) = Т₂(Т₁(И))

В начале к слову И применяется машина Т₁, а потом к результату работы машины Т₁, применяется машин Т₂.

Ограниченно-детерминированную (автоматную) функцию можно задать при помощи канонических уравнений

Эти уравнения позволяют строить по входной последовательности значений переменных выходную последовательность. Значения выходной последовательности находятся постепенно по мере поступления входных значений. Это позволяет трактовать выписанные выше уравнения как описание работы некоторого дискретного преобразователя или автомата, который обладает r состояниями (r – вес о.д. функции) и работает дискретно во времени. Формируя состояние памяти и выходное значение в момент времени t по состоянию памяти в момент времени t - 1 и входным значениям в момент времени t в соответствии с каноническими уравнениями.

Определение вычислимости, предложенное А. М. Тьюрингом, основано на анализе осуществлении алгоритма человеком, в распоряжении которого имеется карандаш и бумага.

Дата добавления: 2015-07-07