Машина Тьюринга и рекурсивные функции. Кацаран Т.К - 34 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

34
СОДЕРЖАНИЕ
Введение ...................................................................................................3
1. Машина Тьюринга .................................................................................7
§ 1. Математическая модель машины Тьюринга ...............................7
§ 2. Работа машины Тьюринга .............................................................10
§ 3. Примеры машин Тьюринга, работающих в алфавите {a, b} ......11
§ 4. Способы задания машин Тьюринга, операции над ними ...........15
§ 5. Задачи и упражнения для самостоятельного решения ...............18
2. Функции, вычислимые по Тьюрингу ...................................................19
§ 1. Описание класса функций .............................................................19
§ 2. Примеры функций, вычислимых по Тьюрингу ...........................20
§ 3. Задачи и упражнения для самостоятельного решения ...............23
3. Рекурсивные функции ...........................................................................25
§ 1. Элементарные функции. Правила подстановки
и примитивная рекурсия .................................................................................25
§ 2. Правило взятия μ-оператора. Классы функций ...........................29
§ 3. Теорема о совпадении классов частично-рекурсивных
и вычислимых по Тьюрингу функций ...........................................................31
§ 4. Задачи и упражнения для самостоятельного решения ...............32
Список литературы ....................................................................................33 
                                            СОДЕРЖАНИЕ

      Введение ...................................................................................................3
    1. Машина Тьюринга ................................................................................. 7
        § 1. Математическая модель машины Тьюринга ............................... 7
        § 2. Работа машины Тьюринга ............................................................. 10
        § 3. Примеры машин Тьюринга, работающих в алфавите {a, b} ...... 11
        § 4. Способы задания машин Тьюринга, операции над ними ...........15
        § 5. Задачи и упражнения для самостоятельного решения ...............18
    2. Функции, вычислимые по Тьюрингу ...................................................19
        § 1. Описание класса функций .............................................................19
        § 2. Примеры функций, вычислимых по Тьюрингу ........................... 20
        § 3. Задачи и упражнения для самостоятельного решения ...............23
    3. Рекурсивные функции ........................................................................... 25
        § 1. Элементарные функции. Правила подстановки
и примитивная рекурсия .................................................................................25
        § 2. Правило взятия μ-оператора. Классы функций ...........................29
        § 3. Теорема о совпадении классов частично-рекурсивных
и вычислимых по Тьюрингу функций ........................................................... 31
        § 4. Задачи и упражнения для самостоятельного решения ...............32
    Список литературы ....................................................................................33




                                                        34

Страницы