Проблема самозастосовності

Будемо говорити, що машина Тьюринга М самозастосовна, якщо вона зупиняється на своєму власному коді d (М), і не самозастосовна, якщо вона не зупиняється на своєму коді d (М).

Теорема. Проблема розпізнавання самозастосовності машини Тьюринга алгоритмічно не розв'язна.

Доказ. Припустимо, що побудовано машину Тьюринга М¢, що зупиняється в “ так!” стані, якщо машина самозастосовна, і в “ немає!” стані, якщо не самозастосовна. Тоді в програмі машини Тьюринга присутні дві команди виду: s q ¢ ® s так!, t q ¢¢ ® t немає!

Аналогічно попередньому доказові, побудуємо машину М¢¢, змінивши одну команду: s q ¢ ® s дана (тобто машина не зупиняється, а нескінченно пише символ s на стрічці). Тепер, якщо на вхід М¢ подати d (М¢¢): М¢(d (М¢¢)) машина буде видавати “ так!”, – тобто повідомляти, що М¢¢ самозастосовно, у той час як вона не самозастосовна, тому що не зупиняється, і, навпаки, вона буде видавати повідомлення “ немає!”, якщо машина М¢¢ не зупиняється, тобто якщо вона самозастосовна.

У такий спосіб доказательстно нерозв'язності проблеми самозастосовності зводиться до доказу неможливості розпізнавання останова машини Тьюринга. Звідси виник і загальний метод доказу алгоритмічної нерозв'язності інших задач: метод зведення проблем. У цьому методі нова проблема зводиться до деякої іншої проблеми, для якої вже доведена алгоритмічна нерозв'язність. Особливо часто проблема зводиться в проблемі самозастосовності. Як приклад розглянемо проблему еквівалентності слів в асоціативних вирахуваннях.

Теорема (Маркова – Посади). Існує асоціативне вирахування, у якому проблема розпізнавання еквівалентності слів алгоритмічно нерозв'язна.

Доказ. Нехай машина Тьюринга М починає роботу зі слова R з початковою конфігурацією q₀a і закінчує роботу словом S з кінцевою конфігурацією q_kb. Проблема розпізнавання еквівалентності слів R і S у такій постановці полягає в перебуванні алгоритму, що по коду машини М розпізнає, чи зупиниться вона в стані q_k, починаючи роботу з конфігурації q₀a, чи ні. Подамо код цієї машини разом зі словом R на вхід універсальної машини М¢: М¢(d(M)*R). Для машини М(проблема останова нерозв'язна. Звідси випливає, що проблема розпізнавання еквівалентності слів також алгоритмічно нерозв'язна. Покажемо, що вона нерозв'язна також і в деякому асоціативному вирахуванні. Для цього скористаємося тим властивістю, що для будь-якої машини Тьюринга можна побудувати еквівалентне йому асоціативне вирахування.

Остання властивість була доведена нами для нормальних алгоритмів Маркова. Нормальний алгоритм Маркова можна розглядати як асоціативне вирахування з однонапрвленными підстановками, що непоредственно випливає з визначення цих систем. При необхідності для кожної підстановки нормального алгоритму можна визначити зворотну підстановку й одержати асоціативне вирахування з двунапраленными підстановками.

Побудуємо асоціативне вирахування S (M), що виконує той же алгоритм, що і машина М, зокрема, що переробляє слово R у слово S, і приєднаємо до нього систему підстановок виду q_ka_i®q_k. Одержимо нове вирахування S¢ (M). У цьому вирахуванні також переробляються слова виду R у слова виду S, але всі заключні конфігурації М в S¢ (M) эквивалентнтны. Тому в S (M) слова q₀a і q_k еквівалентні, якщо і тільки якщо машина М, почавши роботу зі слова q₀a, зупиниться. Через нерозв'язність проблеми останова для М¢, проблема еквівалентності слів q₀a і q_k також нерозв'язна.

З цієї теореми випливає, що проблема розпізнавання еквівалентності слів у загальному випадку (тобто для всієї безлічі асоціативних вирахувань) алгоритмічно нерозв'язна. Звідси випливає також, що проблема еквівалентності алгоритмів нерозв'язна: по двох заданих алгоритмах неможливо визначити, обчислюють вони ту саму чи функцію ні.

Історично алгоритмічна нерозв'язність спочатку була встановлена для проблем, що виникають у математичній логіці, – проблем виводимості у формальних теоріях. Доказ нерозв'язності проблем самозастосовності й еквівалентності показав, що алгоритмічні схеми можуть служити апаратом дослідження можливості розв'язання і повноти формальних теорій. Проблему виводимості у формальній теорії можна інтерпретувати як проблему распознаваниия еквівалентності слів: з помошью заданої системи правил висновку необхідно визначити, чи є формула виведеної з заданої системи аксіом і вихідної безлічі посилок. Тоді з алгоритмічної нерозв'язності розпізнавання еквівалентності слів випливає нерозв'язність (у загальному випадку!) проблеми виводимості. Ми знаємо, що вирахування висловлень розв'язне: побудова таблиці істинності формули є алгоритмом, за допомогою якого доводиться, що формула є (або не є) тавтологією логіки висловлень, а, отже, і теоремою вирахування висловлень. Вирахування предикатів 1-го порядку нерозв'язно, що було доведено для формальної арифметики S (теорема Гёделя про неповноту). Доказ теореми Гёделя істотно основывалость на рекурсивності представимых у S функцій і відносин. Отже, той же самий результат можна одержати, використовуючи апарат алгоритмічних схем, зокрема, машини Тьюринга. У 1936 р. цей результат: проблема розпізнавання виводимості алгоритмічно нерозв'язна, – був отриманий Черчем.

Теорема Черча дає конструктивний спосіб побудови невычислимой функції.

Як приклад визначення такої функції розглянемо наступну задачу. Уявимо собі велику бібліотеку, у якій книги розставлені по розділах. Для кожного розділу складений каталог. Кожна книга має призначену їй ціну, а оскільки каталог роздягнула містить зведення про всі книги, він повинний бути самою коштовною книгою. Тому його вартість определна як функція від вартості самою дорогою нкиги в розділі: С_к = С_max + 1. Книг у бібліотеці виявилося настільки багато, що всі каталоги були складені в окремий розділ і був складений каталог каталогів. Йому також повинна бути призначена ціна за визначеним вище правилом: вартість його повинна бути найвищої в цьому розділі, тобто С_к^к = С_кmax, і повинна бути на одиницю більше ціни найдорожчої книги в розділі: С_к^к = С_кmax + 1. Але оскільки каталог каталогів сам є каталогом, те його ціна болжна бути на одиницю більше його власної вартості: С_к^к = С_к^к + 1. Таким чином, виявилося, що вартість його неможливо обчислити за заданим правилом.

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