Невычислимые функції

ЛЕКЦІЯ 5.Теза Черча

Кожна функція є ефективно вычислимой тоді і тільки тоді, коли вона рекурсивна.

Іншими словами, теза Черча пропонує розуміти під ефективної вычислимостью існування алгоритмічної схеми, а оскільки всі знайдені алгоритмічні схеми обчислюють тільки клас рекурсивних (частково рекурсивних) функцій, то під ефективної вычислимостью тоді розуміється рекурсивність.

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

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

Прийняття тези Черча, впевненість у його справедливості заснована насамперед на досвіді: у результаті численних досліджень не удалося знайти якої-небудь іншої алгоритмічної схеми, що обчислювала б більш широкий клас функцій, чим рекурсивний. Усі знайдені алгоритмічні схеми виявилися еквівалентні між собою і, отже, еквівалентні машині Тьюринга. Тому вычислимыми функціями, відповідно до тези Чёрча, є ті і тільки ті, котрі є рекурсивними (частково рекурсивними). Тоді, якщо приймати теза Чёрча, повинні існувати і невычислимые функції.

Теорема. Безліч функцій над словами деякого алфавіту еквівалентно безлічі функцій на безлічі натуральних чисел, а безліч функцій на безлічі натуральних чисел незліченно.

Доказ. Припустимо, існує перерахування L = F ₁, F ₂,…, F_k, …всіх арифметичних функцій (тобто функцій, визначених на безлічі N ). Побудуємо функцію U (n) у такий спосіб:

м 1, якщо F_n (n) не визначена,

U (n) = н

о F_n (n) + 1, у противному випадку.

Тоді U (n) – усюди визначена на N функція. Якщо безліч арифметичних функцій счетно, тобто існує перерахування L, то побудована нами функція входить у це перерахування з яким-небудь номером, наприклад, m, тобто U (n) Î L і U (n) = F_m. Тоді, обчислюючи значення цієї функції від m відповідно до її визначення, одержимо: U (m) = F_m (m): F_m (m) = F_m (m) + 1, якщо F_m (m) визначена, що неможливо, тобто ми прийшли до протиріччя.

Побудована нами функція, по-перше, доводить незліченність безлічі арифметичних функцій, а по-друге, по способі побудови вона є невычислимой функцією.

Таким чином, ми установили, що безліч всіх арифметичних функцій незліченно, тобто його потужність дорівнює 2À₀ = c. Постараємося з'ясувати, яка потужність безлічі всіх рекурсивних функцій. Тепер, коли встановлена еквівалентність усіх рекурсивних функцій і всіх машин Тьюринга, для цього досить “перерахувати” усі можливі машини Тьюринга.

Розглянемо безліч символів, необхідних для зображення програми для машини Тьюринга. Нехай зовнішній алфавіт складається з двох символів: A = {0, 1}(можливість кодування будь-яких даних у двоичной системі числення ні в кого не викликає сумніву – адже саме так працюють сучасні обчислювальні машини). Нехай стани позначаються десятковими числами, тобто внутрішній алфавіт Q = {0, 1, 2, 3, 4, …, 9}, і три символи нам знадобляться для вказівки руху голівки: {П, Л, Н}. Кожній клітці в таблиці, що зображує програму машини Тьюринга, поставимо у відповідність команду у виді: a_iq_j ® червонийzq_д, де a_i,a_k Î A, z Î {П, Л, Н}, q_j, q_д Î Q. Будемо використовувати роздільники:, – для заміни символу ®,; – для відділення однієї команди від іншої. Тоді послідовність команд може бути зображена, наприклад, так: 10, 0П12; 01, 0П1; 11, 1Л2; і так далі. Запис 10, 0П12; означає, що в стані 0 машина бачить символ 1, записує на його місце символ 0, зрушується вправо і переходить у стан 12. Тоді для запису програми машини Тьюринга досить тільки 15 символів (з огляду на, що символи зовнішнього алфавіту 0 і 1 входять і в алфавіт Q). У результаті будь-яка програма може бути представлена, як число в 15-тиричной системі числення.

Записана так, як зазначено вище, програма для машини Тьюринга M називається кодом машини Тьюринга і позначається d(M), а 15-тиричное число, яке можна поставити їй у відповідність, називається індексом машини Тьюринга.

Таким чином, кожній машині Тьюринга можна поставити у відповідність її індекс – число в 15-ричной системі числення. Але безліч чисел у 15-тиричной системі числення счетно (тому що счетна будь-яка нескінченна послідовність кінцевих послідовностей символів), – виходить, безліч усіх машин Тьюринга теж счетно. Отже, потужність безлічі всіх рекурсивних функцій (оскільки вони і тільки вони вычислимы на машині Тьюринга) дорівнює À₀, і À₀ < c.

Ми показали, що всіх арифметичних функцій більше, ніж вычислимых функцій, а звідси випливає, що існують невычислимые функції. У загальному виді це означає існування таких проблем (задач), для яких неможливо побудувати алгоритм, тобто машину Тьюринга, – якщо приймати теза Черча. Це не означає, утім, що ці проблеми взагалі нерозв'язувані. Проблема вважається алгоритмічно нерозв'язної, якщо існує хоча б одна задача з даного класу задач, для якої математично строго доведена неможливість побудови алгоритму, тобто машини Тьюринга, або нормального алгоритму Маркова, або якої-небудь іншої алгоритмічної схеми. Тьюринг запропонував інструмент для доказу алгоритмічної нерозв'язності – універсальну машину Тьюринга.

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