="justify"> - деякий алфавіт, а - натуральне число. Нехай - машина Тьюринга із зовнішнім алфавітом . Побудуємо часткову функцію з в так: , якщо результат роботи машини на вході збігається зі словом . Якщо машина не зупиняється або на стрічці записано небудь не те (наприклад, символи не з алфавіту і т.п.), то не визначена.
Визначення 1.2. Часткова функція з в називається обчислюваною, якщо існує машина Тьюринга , для якої .
Предикат від декількох змінних дозволимо, якщо його характеристична функція вичіслімих.
Нас цікавитимуть ресурси, потрібні для обчислень. Два найважливіших ресурсу - час і пам'ять. Будемо говорити, що машина Тьюринга працює за час , якщо максимальне (за всіма входів довжини ) кількість тактів, яка пропрацює до зупинки, дорівнює . Аналогічно, машина Тьюринга працює на пам'яті , якщо найбільш віддалене від початку стрічки положення голівки при обчисленнях на входах довжини < span align = "justify"> дорівнює .
Обчислення на машинах Тюрінга.
Очевидно, що МТ задає алгоритм у значенні наведеного вище неформального визначення. Протилежне твердження називається тезою Черча:
"будь-який алгоритм може бути реалізований машиною Тьюрінга"
Не вдаючись в обговорення тези Черча, зауважимо, що в даний час немає серйозних підстав піддавати його сумніву. Всі відомі в даний час алгоритми реалізуються машинами Тьюрінга. Детальний виклад теорії алгоритмів читач може знайти в книгах [<# "16" src = "doc_zip285.jpg"/>, яка, отримуючи на вхід пару, дає вихід. Тут через позначено опис деякої машини Тьюринга. Дійсно, припустимо, що зошит починається зі сторінок, де записані інструкції по роботі. Тоді виконувати ці інструкції можна таким чином: пометим поточну сторінку; перегорнемо зошит до початкового розділу, що містить інструкції; знайдемо потрібну інструкцію; повернемося назад і виконаємо її. p> Сложностние класи.
Чи не для всякої обчислюваної функції можна реально здійснити обчислення її значення. Існування алгоритму не означає, що нам під силу виконати всі визначені дії. Перешкода мож...
