Машини Тьюринга і рекурсивні функції
Ми розглянули кілька різних прийомів побудови примітивно рекурсивних функцій. Проте залишається не зовсім зрозумілим, наскільки цей клас широкий. Зараз ми покажемо, що він включає в себе все досить швидко обчислюваної функції.
Теорема 75. Будь-яка функція. обчислювана на машині Тьюринга не більше ніж за примітивно рекурсивне (від довжини входу) час, примітивно рекурсивна.
Нагадаємо, що ми вважаємо входом і виходом машини Тьюринга слова з нулів і одиниць. Оскільки аргументами і значеннями примітивно рекурсивних функцій є числа, теорема матиме сенс, тільки якщо ми домовимося ототожнювати числа і слова. Як вже говорилося, ми ототожнюємо число n зі словом, яке виходить після видалення старшого біта 1 в двійковому розкладанні числа n + 1.
При імітації роботи машин Тьюринга за допомогою програм ми кодували стан машини чотирма числами (код лівій частині стрічки, код правій частині стрічки, стан і буква під головкою). При цьому зручно було таке кодування. ліву частину стрічки ми вважали записом числа в системі числення, в якій основа дорівнює числу символів в алфавіті машини, а пробіл вважається нулем; з правою частиною стрічки ми поступали так само, тільки в зворотному порядку (молодші розряди у головки). При цьому додавання або вилучення символу у головки відповідало простою арифметичною операції (видалення це поділ остачі, додавання множення на підставу системи числення і додавання). При такому кодуванні функції переходу (чотири функції чотирьох аргументів, що показують наступне стан як функцію попереднього), записуються простими формулами і примітивно рекурсивних.
Тепер розглянемо ітерованих функцію переходу, яка говорить, якою буде стан машини Тьюринга після t кроків. Точніше, тут є чотири функції від п'яти аргументів (перші чотири аргументи кодують стан, п'ятий являє собою число кроків). Їх визначення має вигляд спільної рекурсії, яку ми тільки що розібрали. Тому ці функції примітивно рекурсивних. Будемо вважати, що після появи заключного стані конфігурація машини не змінюється. Якщо ми знаємо, що число кроків роботи обмежена примітивно рекурсивної функцією. то досить підставити її на місце п'ятого аргументу (числа кроків), щоб переконатися, що заключна конфігурація машини є примітивно рекурсивної функцією від її початкової конфігурації. Отже, результат роботи є примітивно рекурсивної функцій початкового даного.
Це міркування неявно використовує примітивну рекурсивность різних функцій, пов'язаних з переходом від одного представлення даних до іншого. Наприклад, вхід машини Тьюринга є двійковим словом, яке ми домовилися ототожнювати з деяким числом x. Цьому входу відповідає початкова конфігурація машини Тьюринга, яку ми кодируем четвіркою чисел. Нам важливо, що ця четвірка примітивно рекурсивно залежить від x. Це легко зрозуміти, так як перетворення пов'язане з переходом від однієї системи числення до іншої (одне і те ж слово кодує різні числа в різних системах числення); примітивну рекурсивность таких функцій легко встановити за допомогою описаних вище методів. Крім того, нам треба з вихідний конфігурації примітивно рекурсивно витягти результат і також перекодувати його, а також по входу отримати його довжину (щоб підставити в примітивно рекурсивную функцію, що обмежує число кроків). Але все це також не виходить з кола розібраних вище прийомів, і докладно зупинятися на цьому ми не будемо.
Ця теорема переконує нас у примітивній рекурсивності багатьох досить складно обумовлених функцій. Наприклад, розглянемо функцію n (n -ий десятковий знак числа). Відомо, що обчислені мільйони таких знаків, тому є всі підстави вважати, що відомі алгоритми працюють не дуже довго було б дуже дивно, якби час їх роботи (навіть з огляду на незручність машини Тьюринга для програмування) не оцінюються б, скажімо, функцією cx 2 n при досить великому c. А така оцінка примітивно рекурсивна, що дозволяє послатися на тільки що доведену теорему. (Насправді тут великий запас існують примітивно рекурсивні функції. Які ростуть набагато швидше 2 n.)
Друге окреслення класу примітивно рекурсивних функцій. більш зрозуміле програмістам: це функції, які можна обчислювати програмою, що містить if-then-else -ветвленія і for -Цикли, але не містять while -Цикли (і тим більше go to і різних інших капостей типу зміни параметра for- циклу всередині циклу) .
87. Сформулюйте і доведіть відповідне твердження.
Частково рекурсивні функції
Оператори примітивної рекурсії і підстановки не виводять нас з класу всюди певних функцій. Не так стоїть справа з оператором мінімізації. про який ми вже згадували. Він застосовується до (k + 1) -Місцеві функції f і дає k -Місцеві функцію g. яка визначається так: g (x1. xk) є найменше y. для якого f (x1. xk, y) = 0.
Сенс виділених слів ясний, якщо функція f всюди визначена. Якщо немає, то розуміти їх треба так: значення g (x1. Xk) одно y. якщо f (x1. xk, y) визначено й дорівнює нулю, а все значення f (x1. yk, y ') при y' Часто використовується позначення і тому оператор мінімізації також називають-оператора. Ясно, що таке визначення забезпечує вичіслімость g. якщо обчислюваності f (ми перебираємо в порядку зростання всі y. чекаючи появи нульового значення). 88. Покажіть, що якщо змінити ухвалу і вирішити f (x1. Xk, y ') бути не визначеним при y' Функції, що виходять з базисних (нуля, проекції і додавання одиниці) за допомогою операторів підстановки, примітивної рекурсії і мінімізації, називаються частково рекурсивними. Якщо така функція виявляється скрізь певної, то її називають общерекурсівной функцією. Така дивна термінологія, мабуть, склалася в результаті перекладів з англійської. По-англійськи були "primitive recursive functions" (примітивно рекурсивні функції). Потім було дано більш загальне (general) поняття обчислюваною всюди певної функції, і такі функції були названі "general recursive functions". Потім стали розглядати і часткові (partial) обчислюваної функції, називаючи їх "partial recursive functions". У російській же мові слово "partial" попало не туди, і замість часткових рекурсивних функцій стали говорити про частково рекурсивних функціях. Та ж доля спіткала і слово "general", яке дивним чином увійшло в прикметник "общерекурсівная" і означає, що функція всюди визначена. Теорема 76. Будь-яка функція. обчислювана за допомогою машини Тьюринга, є частково рекурсивної. Нехай f обчислювана за допомогою машини Тьюринга (позначимо цю машину через M) функція одного аргументу. Розглянемо властивість T (x, y, t). що складається в тому, що машина M на вході x дає відповідь y за час не більше ніж t. Як ми бачили вище, по входу машини Тьюринга і за часом t можна примітивно рекурсивно обчислити її стан в момент t; ясно, що можна також дізнатися, закінчила вона роботу, і якщо так, то чи була відповідь дорівнює y. Отже, властивість T примітивно рекурсивно. Тепер об'єднаємо аргументи y і t в пару за допомогою примітивно рекурсивної нумерації; вийде примітивно рекурсивна функція T '. для якої T '(x, [y, t]) = T (x, y, t); тепер можна написати, де p1 дає по номеру пари її перший член, а означає "найменше z. для якого.". Таким чином, функція f є частково рекурсивної. Вірно і зворотне: Теорема 77. Будь-яка частково рекурсивна функція обчислюваних на машині Тьюринга. Легко написати програму з кінцевим числом змінних, яка обчислює будь-яку частково рекурсивну функцію (підстановка зводиться до послідовного виконання програм, рекурсія до циклу типу for. Мінімізація до циклу типу while; обидва види циклів легко реалізуються за допомогою операторів переходу). Після цього залишається тільки послатися на те, що будь-яка функція. обчислюється програмою з кінцевим числом регістрів, обчислюваних на машині Тьюринга (як ми бачили в розділі 10.2, теорема 66). Тому якщо ми віримо в "теза Тьюринга", який гласить, що будь-яка обчислювана функція обчислюваних на машині Тьюринга, то повинні вірити і в "теза Черча" (всяка обчислювана функція частково рекурсивна), так що ці тези рівносильні. Насправді історія тут складніше і приблизно може бути описана так. Визначення примітивно рекурсивної функції було дано великим логіком Куртом Геделем і використано як технічний засіб при доведенні теореми Геделя про неповноту, на початку 1930-х років. Він же дав визначення общерекурсівной функції (що не співпадає з наведеним нами, але еквівалентне йому). Американський логік Алонзо Черч сформулював свою тезу для усюди певних функцій. припустивши, що будь-яка обчислювана всюди певна функція є общерекурсівной. Потім американський математик Кліні запропонував поширити цю тезу на функції, які не є всюди визначеними. Паралельно англійський математик Тьюринг і американський математик Пост запропонували свої моделі абстрактних обчислювальних машин (машини Тьюринга і Посту), що відрізняються лише деякими деталями, і висловили припущення про те, що такі машини покривають весь клас алгоритмічних процесів. Незабаром стало ясно, що вичіслімость функції на таких машинах рівносильна часткової рекурсивності. (Історичні подробиці можна дізнатися з книги Кліні [4].) Так чи інакше, зараз вирази "теза Тьюринга", "теза Черча", "теза Посту" і т.п. зазвичай вживають як синоніми: ці тези стверджують, що інтуїтивно зрозумілий клас обчислюваних часткових функцій збігається з формально визначеним класом частково рекурсивних функцій (теза Черча), обчислюваних на машинах Тьюринга функцій (теза Тьюринга) і т.д. При такому розумінні можна довести еквівалентність всіх цих тез, так як всі відомі формальні визначення обчислюваності (часткова рекурсивность, машини Тьюринга і т.д.) призводять до одного і того ж класу функцій. (Зауважимо в дужках, що ще одна обчислювальна модель нормальні алгорифм. Або алгоритми Маркова. Були запропоновані Андрієм Андрійовичем Марковим-молодшим (сином старшого, в честь якого названо марковские ланцюга і марковские процеси). Це було вже в 1950-ті роки. Марков писав слово алгорифм через "ф". Відповідний принцип (всякий алгорифм еквівалентний нормальному) він називав принципом нормалізації. В його роботах нормальні алгорифм використовувалися для побудови нерозв'язного асоціативного обчислення. Крім того, Марков реально випіс л у всіх деталях конструкцію універсального алгоритму і провів точний доказ його коректності; здається, це досягнення залишається ніким не повторенням ні у кого більше не вистачило наполегливості, щоб для якоїсь мови програмування написати цією мовою його інтерпретатор і формально довести його коректність.)Схожі статті