Машина, що розпізнає, Тьюринга

Рівнобіжна композиція.

Послідовна композиція.

Нехай М1 і М2 – дві машини Тьюринга. Тоді, ототожнивши заключний стан машини М1 з початковим станом машини М2 і, при необхідності, перенумерувавши внутрішні стани машини М2, одержимо нову машину Тьюринга, що, починаючи роботу зі слова W, спочатку буде виконувати над ним перетворення, виконувані машиною М1, а потім буде працювати як машина М2. Композицію машин Тьюринга можна позначити: M 1°М2 = M 2(М1(W)). Таким чином, послідовна композиція машин Тьюринга здійснює суперпозицію функцій.

Якщо на стрічці записане слово W, що представимо як конкатенація двох слів Р||Q, можна скласти таку машину Тьюринга, що буде працювати як машина M 1 над подсловом P і як машина M 2 над подсловом Q, а потім здійснить конкатенацію результатів: M 1(P)|| M 2(Q).

Якщо існують машини Тьюринга M 1 і M 2 і машина, що розпізнає, Тьюринга P, то можна скласти таку машину Тьюринга M, що, починаючи роботу зі слова W, машина работает працює спочатку що як розпізнає машина P ( W). Якщо вона закінчує обробку вихідного слова в стані так, то далі працює машина M 1(W), а якщо в стані ні, те машина M 2(W).

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