Примитивни рекурсивни функции (PRF)

Определение. Начални функции се наричат:

1) постоянна функция. където п = 0,1,2, ..., р = 0,1,2, .... по-специално нула функция.

2) следната функция.

3) Изберете функция. където 1≤ m ≤ п, п = 1,2, ....

Всички елементарни функции - навсякъде определени и алгоритмично

изчислима. Има малък брой операции на елементарните функции, които са изчислима функция изчислима отново.

Операция заместване (суперпозиция)

Като се има предвид функция и функция. Твърди се, че функцията, получени от тези функции чрез заместване на операцията, ако следното уравнение

и е обозначен с. където S - е операцията по замяна.

Пример. Да. след това

Основните характеристики на работата на заместване

1. операция заместване запазва свойството навсякъде определени функции, т.е.. Е. Ако функция ж (y1, ..., YM) и функции h1 (х1, ..., хп), h2 (х1, ..., хп), HM (х1, ..., хп) навсякъде дефинирана функция е и функцията на който се получава от действието на заместване, след това е също функция дефинирано навсякъде.

2. Работа смяна запазва собственост на алгоритмична изчислимост от функции, т.е. Ако функция г (y1, ..., YM) и h1, ..., хм са алгоритъм изчислимо и F = S (G; h1, ..., HM), тогава съществува алгоритъм Af. изчислява функцията F.

Действието на примитивна рекурсия

Нека функцията и функцията.

Определение. Говори се, че функцията, получена от функциите, както и от работата на примитивна рекурсия ако следните равенства притежават:

Това има смисъл, когато N ≠ 0, записаните

При задаване на примитивно рекурсивни описание функция. независими от една променлива схема примитивна рекурсия има формата

Клас PRF всички примитивно рекурсивни функция е набор от функции, които могат да бъдат получени от първоначалните функции чрез наслагване и примитивна рекурсия.

Основни свойства на операция примитивна рекурсия на

1) Операция примитивна рекурсия, както и операцията за смяна запазва собствеността навсякъде сигурност и алгоритмично изчислимост.

2) Опазване на Изчислимост алгоритмични функции.

Пример. Нанесете на работата на примитивна рекурсия на функцията. Функция писано в "аналитичен" форма.

Решение. , , Според примитивна операция рекурсивно. ,

Нека ти стъпка, за да е истина. след това

По този начин, в резултат на примитивна рекурсия.

III. Тюринг машина

Алгоритъм - се определя по някакъв краен езиково обучение (процес рецепта), който определя изпълнимия дискретна последователност от елементарни операции за решаване на проблема. Процесът на изпълнение на инструкции се състои от отделни етапи, всеки от които притежава следващата операция.

В същността си, алгоритъмът е механичен процес на обработка на информацията. За първи път, Алън Тюринг е дефинирано понятието алгоритъм, базиран на концепцията за автоматичен машина; Освен това, той предложи официално модел на устройството, което е интуитивно симулира човешки действия решава проблема, като се ръководи от някои алгоритъм. Това устройство е наречено Тюринг машина.

В изчислително устройство Тюринг моделира, довел до най-основните операции в процес на изпълнение на произволен алгоритъм човек. Мъжът е с краен памет, и в този смисъл е възможно да си представим една система с краен брой състояния. Основна информация за алгоритъма обикновено е представен като поредица от букви. Можем да си представим, че тази информация е представена под формата на думи (крайна поредица от знаци) в краен лексика. Извършване алгоритъм човек калкулатор използва допълнителна памет (които могат да бъдат потенциално безкрайна, например хартия) за записване на информация, и този запис се извършва последователно знак по знак. При изчисленията, човек може да се върне в предварително записана информация, изтривайки част от информацията и т.н. По този начин, когато елементарни операции на алгоритъма може да се предполага запис и изтриване характер, както и изместване на вниманието от една област в друга запис. Тюринг предложен модел има един безкраен работа лента, която чете и записва знаци и където за четене и запис на главата, която може да се движи върху работната лента в двете посоки.

Тюринг машина Сега ще опишем по-подробно. Машината е с краен брой цифри (знаци, букви), образувайки така наречената външна азбука A =. Във всяка клетка от изследваните ленти във всяка дискретна момент може да се запише само един символ на азбука А. За по-голяма еднородност е удобно да се предположи, че сред буквите от азбуката А, има външна "празен писмо", и че той се записва в празната клетка на лентата. Ние сме съгласни, че "празна буква" или символа на празните клетки е буквата # 923;. Лентата се приема неограничен и в двете посоки, но във всеки един момент върху него писмено не е празен краен брой писма

Освен това, всеки път, когато машината е в състояние да бъде в състояние на краен брой вътрешни състояния, които се определят от Q =. q1 начална и крайна (или спре състояние) q0 - разпределят между две държави. Да бъдеш в състояние на Q1, устройството ще започне да работи. Веднъж в състояние q0, машината спира.

Действието на устройството, определена от програмата (функционална блокова диаграма). Програмата се състои от команди. Всеки отбор T (I, J) (I = 1, 2. п; J = 0, 1 м) е израз на един от следните видове :. къде. и X =.

Следващия път, когато (ако Qk ≠ q0) машина прави стъпка,

регулиран команда T (л, к): alqk → asqrX т.н.

Тъй като работата на машината, от предположение, че е напълно определя от неговото състояние QJ в момента и съдържанието на изследваните клетки в този момент, след това за всяка QJ и AI, (I = 1, 2. п; J = 0, 1. т) програма машина трябва съдържат една и само една команда като се започне символи qiaj. Следователно Тюринг програма машина с азбука А = външни и вътрешни състояния азбука съдържа Q = М (п + 1) команда.

Една дума от азбуката или азбука Q, или азбука AUQ отнася до всяка последователност на съответната азбука. При конфигурирането на к-то имаме предвид имиджа на лентата на машината със съществуващата върху него в началото на етапа на к-тия информация (или дума в азбука А, записано на лента в началото на етапа на к-ти), което показва, коя клетка е изследвано в тази стъпка и състоянието на машината. Има смисъл само крайната конфигурация, т.е. тези, при които всички лентови клетки, с изключение може би за краен брой, празен. Конфигурацията се нарича окончателен, ако държавата, в която се намира на машината, окончателно.

Ако изберете някоя не окончателната конфигурация на машината на Тюринг като оригинала, работата на машината ще се състои във факта, че серията (стъпка по стъпка), за да я превърне в оригиналната конфигурация, в съответствие с програмата на машината, докато, докато стигнете до крайната конфигурация. След това работата на машина на Тюринг се счита за приключила и се счита за резултат от работата да се достигне крайната конфигурация.

Ние казваме, че не е празна дума # 945; в азбука A \ = възприема машина в нормално положение, ако е записано в последователни клетки ленти, всички други клетки са празни, а устройството сканира най-дясната клетка от тези, в които писаното слово # 945;. Стандартната позиция се нарича първоначалния (крайно), ако машината, да вземе думата в нормално положение, че е в изходно състояние Q1 (съответно q0 спирка състояние). И накрая, ние казваме, че думата # 945; машини за текстообработка # 946;, ако думата # 945;, възприемана в първоначалния стандартно положение, машината след краен брой отбори идват на думата # 946;, възприемана в положение стоп.