Композиція машин Тьюринга

ЛЕКЦІЯ 3. Машина, що розпізнає, Тьюринга

Машина, що розпізнає, Тьюринга - це машина, що обчислює предикат P(W) таким чином, що якщо P(W) = T, те машина зупиняється в стані так!, а якщо P(W) = F, те в стані немає!.

Наприклад, машина, що розпізнає парність числа, представленого в унарной системі числення, приведена нижче в таблиці. Рухаючи ліворуч праворуч, машина зупиняється на порожньому символі в стані так!, якщо число парне, і в стані немає!, якщо непарне.

Можна виділити деякий набір елементарних алгоритмів, з яких можна одержувати більш складні алгоритми за правилами композиції машин Тьюринга. Ми вже показали, що елементарні функції

· Нуль-функція 0(x)= L;

· Додавання символу z: P_z(x) = xz, де z Î A;

· Функція, що проектує, Uij(x) = xi;

· Тотожне перетворення Т (x) = х;

· Алгоритм копіювання слова Copy (x) = x * x;

· Алгоритм, що заміняє, Repxjxi ( x) = xj, де xi, xj ( A ( B, де B - допоміжний алфавіт.

З цих елементарних алгоритмів можна утворювати більш складні за допомогою композиції машин Тьюринга.

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