ся в двійковій системі числення і перераховуються через кому; два многочлена поділяються зірочкою: 1, 0, -101 * -100, 1. Таким чином, ми маємо дві різні обчислювальні завдання. З практичної точки зору, обидва завдання еквівалентні, оскільки переклад з одного кодування в іншу здійснюється за допомогою поліноміальною алгоритму. Поки визначення поліномального алгоритму у нас немає, давайте будемо формалістами: обчислювальна задача - це частічная1) <# "16" src = "doc_zip187.jpg"/> (де позначає безліч кінцевих слів у алфавіті). Потім ми дозволимо собі деяку вільність і будемо говорити про завдання множення многочленів або розкладання цілого числа на множники, маючи на увазі, що всі розумні кодування еквівалентні (тобто переводяться один в одного за допомогою поліноміальних алгоритмів). Однак потрібно пам'ятати, що не всяка кодування є "розумною". Недобре, наприклад, представляти натуральне число набором з зірочок, бо довжина такого запису експоненціально велика в порівнянні з двійковій або десятковій записом. Зауважимо також, що в деяких завданнях немає хорошого вибору "розумної" кодування, в таких випадках (вони нам не зустрінуться) необхідно вказувати кодування щоразу, коли формулюється завдання. p> Тепер дамо формальне визначення алгоритму.
Машини Тюрінга.
Машина Тьюринга (скорочено МТ) однозначно задається вказівкою набору, де,, - кінцеві множини, причому; - деякий елемент; - деякий елемент, а - деяка (часткова, взагалі кажучи) функція з в.
Складові частини МТ називаються так:
- алфавіт,
- порожній символ (або пробіл),
- зовнішній алфавіт,
- безліч станів керуючого пристрою,
- початковий стан,
- функція переходів.
Стан МТ задається трійкою, де - нескінченне слово в алфавіті, тобто довільна послідовність елементів; - невід'ємне ціле число;. Символи слова будемо, як це прийнято, представляти записаними на стрічці, розбитою на клітинки, по комірці на символ. На стрічці також є головка, яка розташована над осередком з номером. Наочно це зображується так:
В
Малюнок 1.1: Стрічка, розбита на клітинки
Крім стрічки машина Тьюринга має управляючий пристрій, стан якого задається елементом множини.
Стани МТ змінюються дискретно. За один такт роботи управляючий пристрій виконує наступні дії (вважаємо, що МТ знаходиться в стані):
читає символ, що знаходиться під головкою (тобто визначає);
обчислює значення функції переходів: (якщо функція переходів на парі не визначена, то зупиняє машину Тьюринга);
записує на стрічку в клітинку символ, зрушує голівку на і переходить в стан (іншими словами, новий стан машини задається трійкою);
якщо, то зупиняє машину.
Мабуть, кожен погодиться, що ці дії не вимагають ні розуміння, ні мистецтва, ні винахідливості.
Робота машини Тьюринга буде завжди починатися зі стану, де за кінцевим словом, що складається з символів зовнішнього а...
