Логика. логіка. Математична логіка та теорія алгоритмів
 Скачать 1.6 Mb.
|
|
Приклад 14. За допомогою оператора мінімізації побудувати арифметичну функцію двох змінних ) , ( y x f , якщо задана часткова арифметична функція z y x z y x g ) , , ( Покладемо, наприклад, x=5, y=9. Знайдемо z таке, що ) 0 9 5 ( z z Вибираючи послідовно z=0,1,2,..., перевіркою встановлюємо, що 16 ) 0 9 5 ( z z , при цьому 2 ) ( x y z . Отже, шуканою функцією буде 2 ) ( ) 0 ( ) , ( x y z y x y x f z Приклад 15. Для функції y x y x f ) , ( знайти таку функцію ) , , ( z y x g , що 0 ) , , ( ) , ( z y x g y x f z Такою функцією, очевидно, буде z y x z y x g ) , , ( , адже ) 0 ( ) , ( z y x y x y x f z Запитання для самоконтролю 1. Яка функція називається арифметичною; всюди визначеною; частково визначено? 2. Яка функція називається обчислювальною? 3. Які функції належать до базових арифметичних функцій? 4. Що називають операцією суперпозиції? 5. Що називають операцією примітивної рекурсії та що являє собою схема примітивної рекурсії? 6. Що називають операцією мінімізації? 113 7. Яка функція називається примітивно рекурсивною, загально рекурсивною, частково рекурсивною? 8. Як формулюється гіпотеза Черча? ВПРАВИ 4.19. Чи буде примітивно рекурсивною функція y x ? 4.20. Довести, що кожна функція, яка тотожно дорівнює натуральному числу n, є примітивно рекурсивною. 4.21. Нехай функція ) (x sg визначена за допомогою таких рівностей: 0 , 1 , 0 , 0 ) ( x x x sg Чи буде ) (x sg примітивно рекурсивною функцією? 4.22. Довести таку рівність: x x sg 1 ) ( 4.23. Довести, що функція x a x f ) ( є примітивно рекурсивною. 4.24. Нехай ) , min( y x - функція двох аргументів, що дорівнює меншому з пари } , { y x , або одному з них, якщо х=у. Довести, що функція ) , min( y x є примітивно рекурсивною. 4.25. Функція ) (x визначає число всіх простих чисел, які не перевищують натурального числа х. Чи є ) (x примітивно рекурсивною функцією? 4.26. Показати, що якщо функція ) ,..., , ( 2 1 n x x x g є примітивно рекурсивною, то наступні функції також примітивно рекурсивні: а) n x i n n i x x x g x x x f 0 1 2 1 2 1 1 ) , ,..., , ( ) ,..., , ( ; б) ) , ,..., , ( ) ,..., , ( 0 1 2 1 2 1 2 n x i n n i x x x g x x x f 4.27. Довести, що характеристична функція ) ( x довільної скінченної множини натуральних чисел є примітивно рекурсивною функцією. 4.4. МАШИНА ТЬЮРИНГА Розглянемо ще одне уточнення змістовного поняття алгоритму, так звану машину Тьюрінга (МТ), яке було запропоноване в 1937 році. МТ – це така алгоритмічна система, в якій правила, що визначають дію алгоритма, побудовані за командно-адресним принципом, аналогічно сучасним комп'ютерам. МТ має два скінченних алфавіти: зовнішній } ,..., , { 1 0 n a a a A і внутрішній } ,..., , { 1 0 n g g g Q . У зовнішньому алфавіті записується вхідна, проміжна та вихідна 114 інформація. Внутрішній алфавіт призначений для позначення (кодування) так званих внутрішніх станів машини. Вхідна інформація записується на нескінченній в обидві сторони стрічці пам’яті, яка розбита на окремі комірки, в кожній з яких записується одна буква. Вважається, що серед букв зовнішнього алфавіту є і пуста буква, яку будемо позначати символом . Пусту букву, як правило, писати не будемо. МТ має зчитуючий елемент (ЧЕ), який будемо зображати стрілкою Читаючий елемент в кожний такт роботи МТ фіксує одну комірку інформаційної стрічки. Серед букв внутрішнього алфавіту (станів) } ,..., , { 1 0 n g g g Q виділяється початковий стан 0 g і, так званий, заключний стан, який означає зупинку машини. Його будемо позначати символом !. Елементарними операціями, які може виконувати МТ, є такі: 1) зчитування букви i a , записаної в комірці, що розглядається ЧЕ; 2) заміна букви i a на A a r (можливий варіант, що i=r); 3) зсув ЧЕ вздовж стрічки на одну комірку вправо (П) або вліво (Л) або зсуву взагалі немає (Н). в останньому випадку ЧЕ продовжує оглядати ту ж саму комірку; 4) перехід зі стану j g , в якому машина перебувала на початку роботи команди, в стан k g (можливий варіант, що j=k). Називатимемо конфігурацією МТ зображення стрічки пам'яті з розташованими на ній буквами зовнішнього алфавіту і відміченою ЧЕ (стрілкою) коміркою та фіксацією стану, в якому знаходиться машина. Наприклад, конфігурація може мати такий вигляд: 2 a 1 a 3 a 1 a j g або 2 1 3 1 j a g a a a Реалізація алгоритму в машині Тьюрінга відбувається за допомогою програми роботи цієї машини, яка являє собою набір команд – п'ятірок символів P g a g a k r j i . Ця п'ятірка символів означає, що ЧЕ, знаходячись в стані j g і сприймаючи записану в клітці стрічки букву i a замінює її новою буквою r a (можливий варіант, що i=r), машина переходить в новий стан k g (можливий варіант, що j=k), а ЧЕ зсувається вздовж стрічки на одну клітку в залежності від значення Р, де Р={Л, П, Н} - одна з команд зсуву ЧЕ. 115 На кожному такті роботи МТ інформація обробляється в так званому логічному блоці, який має два входи - i a і j g , і три виходи: r a , k g і Р. Очевидно, що логічний блок реалізує функцію P g a g a f k r j i ) , ( , область визначення і область значень якої скінченні, а тому цю функцію зручно задавати у вигляді прямокутної таблиці, в рядках якої записані букви зовнішнього алфавіту, а в стовпчиках - букви внутрішнього алфавіту (стани). В кожній клітці такої таблиці будемо записувати відповідну вихідну трійку символів. Цю таблицю називають функціональною схемою машини Тьюрінга (ФС). Її заданням робота МТ визначається однозначно. Приклад 1. Побудувати МТ (скласти її функціональну схему), яка реалізує функцію слідування S(n)=n+1, де n - натуральне число, записане в алфавіті {I}. Зовнішнім алфавітом цієї машини буде алфавіт А={I}. Нехай початкова конфігурація машини має вигляд: 0 n g I , тобто в початковому стані 0 g ЧЕ машини оглядає комірку, в якій записана перша зліва одиниця вхідного числа. Змістовно можна запропонувати один з таких алгоритмів: одиниця залишається без зміни, ЧЕ зсувається вправо до тих пір, поки не зустріне першу справа пусту клітку, в яку потрійно записати одиницю. Результат отримано, машину треба зупинити. Відповідна функціональна схема має вигляд: Q A 0 g I ІП 0 g ІН! Будемо вважати, що МТ має стандартний початок роботи, якщо перед початком роботи ЧЕ машини оглядає першу зліва пусту клітку, що передує вхідному слову, і стандартний кінець роботи - після закінчення роботи машина повертається в стандартний початок. Тоді функціональна схема, щореалізує функцію слідування, запишеться так: Q А 0 g 1 g 2 g I ІП 1 g ІЛ 2 g П 1 g ІЛ 2 g Н! Домовимось про деякі спрощення в запису функціональних схем: можна відмовитись від повного запису вихідної трійки P g a k r , опускаючи знаки i a і j g , 116 які не відрізняються від відповідних вхідних знаків, а також не будемо в схемі записувати символ Н, який вказує на відсутність зсуву. З урахуванням цих спрощень попередня схема набуде такого вигляду: Q A 0 g 1 g 2 g I П Л П 1 g ІЛ 2 g ! Приклад 2. Побудувати МТ, що реалізує додавання двох натуральних чисел m і n, записаних в алфавіті {I}. Наприклад, вхідним є слово II III , а початкова конфігурація нехай буде такою: 3 2 0 * g I I Змістовно, суму двох натуральних чисел IIIII II III m n можна, зокрема, одержати таким способом. В числі n зліва направо стираємо послідовно одиниці, записуючи їх справа від m, в результаті чого одержимо слово IIIII . Далі в цьому слові треба зітерти букву і зупинитись. Алгоритм додавання двох натуральних чисел при вказаній вище початковій конфігурації реалізується наступною ФС: Q A 0 g 1 g 2 g I П 1 g ІП 1 g ІЛ 2 g П 0 g ІН 2 g Н 0 g Н! П 1 g Л 2 g Від цієї функціональної схеми досить просто перейти до відповідної функціональної схеми із стандартним початком та стандартним кінцем роботи, для цього потрібно ввести додаткові стани і поповнити ФС новими командами. Приклад 3. Нехай маємо два алфавіти } , { b a A і } , { Г , між буквами яких, встановлена бієктивна відповідність. Побудувати машину Тьюрінга, яка переводить слово в алфавіті А в слово в алфавіті Г (алгоритм перекладу). ФС цього алгоритму із стандартними початком і кінцем роботи має вигляд: Q A 0 g 1 g 2 g a П b П Л 117 Л П 1 g Л 2 g ! В пустих клітках функціональної схеми може буди записана будь-яка інформація, яка на роботу МТ не впливає. Приклад 4. Побудувати МТ, що подвоює натуральні числа, записані в алфавіті {I}. Нехай початкова конфігурація така: 1 0 n I g I . Змістовно кожну паличку будемо замінювати по черзі на зірочку, дописуючи в кінці слова ще одну зірочку. В результаті ми одержимо 2n зірочок. На останньому етапі кожну зірочку замінимо на паличку і зупинимось. ФС шуканої МГ матиме такий вигляд: Q A 0 g 1 g 2 g I П 1 g ІН 0 g ІП 0 g П 1 g Л 2 g Л 2 g !Н Приклад 5. Побудувати МТ, яка будь-яке натуральне число 2 n перетворює в число n-2. Нехай початкова конфігурація така: 0 n g I , тобто машина знаходиться в стандартному початку роботи. Складемо ФС, що реалізує вказаний алгоритм і має стандартний кінець роботи: Q A 0 g 1 g 2 g 3 g I П 2 g П 3 g Л 3 g П 1 g ! Приклад 6. Нехай в алфавіті } , , { b a A задане вхідне слово Q P , де P, Q- слова в алфавіті } , { b a . Побудувати таку МТ, що МТ Q Q P В ролі початкової конфігурації виберемо таку: 0 * g bab aab ФС шуканої МТ така: Q A 0 g a П 0 g 118 b П 0 g Н 0 g ! Наведені приклади алгоритмів свідчать про те, що багато відомих алгоритмів задаються машиною Тьюрінга як точним математичним об’єктом. Виникає питання, а чи будь-який алгоритм (у змістовному розумінні) може бути заданий деякою МТ. Відповідь на це дає гіпотеза Тьюрінга: для будь-якого алгоритму існує МТ, що його реалізує. Очевидно, що гіпотеза Тьюрінга не є математичкою теоремою. Її обґрунтування аналогічне обґрунтуванню принципу нормалізації Маркова та гіпотези Черча. До того ж, всі розглянуті нами уточнення поняття алгоритму (нормальні алгоритми, частково рекурсивні функції та машини Тьюрінга) еквівалентні між собою. Важливе теоретичне значення має факт існування в кожній алгоритмічній системі, в якій поняття алгоритму є математично точним, так званого універсального алгоритму, який може виконувати роботу будь-якого конкретного алгоритму. Зокрема, можна побудувати універсальну машину Тьюрінга (УМТ), яка може виконувати роботу будь-якої конкретної МТ. Для цього на вхід УМТ потрібно подати два слова, одне з яких є кодом ФС конкретної МТ, а друге - код її вхідного слова в деякому стандартному, наприклад, двійковому алфавіті. Із існування УМТ слідує теоретичний висновок (30-і роки ХХст.) про можливість побудови програмного автомата, який би виконував роботу будь- якого алгоритму. Такими автоматами є сучасні комп'ютери. На закінчення відмітимо, що тепер, при наявності точного поняття алгоритму питання про неіснування алгоритму розв'язку тієї чи іншої задачі (масової проблеми) стає математичною теоремою. Доведення теореми про алгоритмічну нерозв'язність певного класу задач означає, що не існує і ніким, і ніякими засобами не можна побудувати єдиного алгоритму, яким розв'язуються всі задачі даного класу. На сьогодні уже відомо багато алгоритмічно нерозв'язних проблем, зокрема, такими є: 1) проблема розпізнавання самозастосовності алгоритмів; 119 2) проблема розпізнавання анулювання для будь-якого алгоритму; 3) проблема розпізнавання застосовності алгоритму до того чи іншого слова; 4) комбінаторна проблема Е.Поста; 5) проблема тотожності слів для півгруп (із скінченним числом твірних елементів і скінченним числом визначальних співвідношень); 6) проблема тотожності слів для груп; 7) проблема представлення для матриць; 8) 10-а проблема Гільберта та ін. Алгоритмічна нерозв'язність всіх вказаних проблем доводиться, виходячи із припущення про справедливість гіпотез Черча, Тьюрінга та Маркова. Існування алгоритмічно нерозв'язних проблем означає, що при пошуку алгоритму розв'язку тієї чи іншої проблеми треба мати на увазі. що такого алгоритму можливо взагалі не існує. Тому поряд із спробами побудови такого алгоритму треба одночасно прагнути довести його неіснування. Алгоритмічна нерозв'язність задач того чи іншого класу зовсім не означає неможливості розв'язати будь-яку конкретну задачу із цього класу. Мова йде про неможливість розв'язування всіх задач даного класу одним і тим же методом. Цілком можливо, що існують алгоритми для розв'язування окремих підкласів таких задач. Тому в таких випадках проблема формулюється стосовно більш вузького класу задач. Наприклад, якщо проблема тотожності слів, як відомо, є алгоритмічно нерозв'язною для класу всіх скінченно породжених груп, то ця проблема тотожності може ставитись для окремих підкласів груп, зокрема, скінченно породжених абелевих, нільпотентних, циклічних, локально-скінченних і т.д. груп. Головне тут полягає в тому, щоб відшукати найбільш широкий клас груп, для якого проблема тотожності розв'язується позитивно. Пошук максимально широких класів задач, для яких та чи інша проблема розв'язується позитивно, є однією із важливих задач розвитку сучасної математики. |