ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.12.2023
Просмотров: 46
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
,... , хn, 1) = f (x1,... ,xп) (начальное условие),
h (x1,... ,хn, k+1) = g(x1,... ,xn, k, h(x1,... ,хn, k)) при k ³ 1 (рекурсивный шаг).
Область определения D(h) описывается также рекурсивно:
г) операция т, которая ставит в соответствие частичной функции f из (N)n+1 в N частичную функцию h из (N)n в N, которая определяется как
Операция т позволяет вводить в вычисления перебор объектов для отыскания нужного в бесконечном семействе.
Теперь, когда введены простейшие функции и элементарные операции, можно дать следующие основные определения:
а) последовательность частичных функций fi, . . . ,fN называют частично рекурсивным (соответственно примитивно рекурсивным) описанием функции fN = f, если fi - одна из простейших функций; fi для всех i ³ 2 либо является простейшей функцией, либо получается применением одной из элементарных операций к некоторым из функций fi,..., fi-1 (соответственно одной из элементарных операций, кроме т);
б) функция f называется частично рекурсивной (соответственно примитивно рекурсивной), если она допускает частично рекурсивное (соответственно примитивно рекурсивное) описание.
Теперь можно привести тезис Черча в обычной форме:
а) функция f полувычислима, если и только если она частично рекурсивна;
б) функция f вычислима, если и только если рекурсивны f и характеристическая функция XD(f).
Характеристическая функция подмножества Х в Y(XÌY) есть такая функция, что
Тезис Черча может использоваться как определение алгоритмической неразрешимости.
Пусть имеется счетная последовательность «задач» P1, P2, ..., которые имеют ответ «да» или «нет». Такая последовательность носит название «массовой проблемы». Свяжем с ней функцию
f из NвN:
Массовая проблема Р называется алгоритмически разрешимой, если функции f и XD(f) частично рекурсивны. В противном случае Р называется алгоритмически неразрешимой.
Контрольные вопросы и задания
1. Для чего необходимо формализовать понятие алгоритма?
2. Что означает фраза: «Машины Поста и Тьюринга являются абстрактными машинами»?
3. Для чего предназначены машины Поста и Тьюринга?
4. Как «устроена» машина Поста?
5. Перечислите и запишите команды машины Поста.
6. С помощью бумаги, карандаша и стиральной резинки «исполните» вместо машины Поста программы сложения чисел из текста.
7. Составьте (и проверьте) программу для машины Поста, создающую на ленте копию заданной последовательности меток справа от нее.
8. Пользуясь предыдущей программой, составьте программу умножения чисел для машины Поста.
9. Как «устроена» машина Тьюринга?
10. Каков принцип исполнения программы машиной Тьюринга?
11. Сравните машины Поста и Тьюринга. Укажите различия.
12. Выполните вместо машины Тьюринга примеры программ из текста.
13. Каким образом могут быть обобщена машина Тьюринга?
14. Что такое ассоциативное исчисление?
15. Постройте дедуктивную цепочку от слова «мука» к слову «торт», заменяя каждый раз по одной букве так, чтобы каждый раз получалось слово.
16. Дайте определение нормального алгоритма Маркова.
17. В чем состоит принцип нормализации алгоритмов?
18. Охарактеризуйте способы композиции нормальных алгоритмов.
19. Как алгоритм может быть связан с рекурсивной функцией?
20. Дайте определения частичной, полувычислимой и вычислимой функции.
21. В чем состоит тезис Черча в слабейшей и в обычной формах?
22. Перечислите простейшие функции.
23. Перечислите элементарные операции.
24. Чем отличается рекурсивная функция от примитивно-рекурсивной?
25. Дайте определение частично-рекурсивной функции.
26. Что называется массовой проблемой? Что означает алгоритмическая разрешимость массовой проблемы?
h (x1,... ,хn, k+1) = g(x1,... ,xn, k, h(x1,... ,хn, k)) при k ³ 1 (рекурсивный шаг).
Область определения D(h) описывается также рекурсивно:
г) операция т, которая ставит в соответствие частичной функции f из (N)n+1 в N частичную функцию h из (N)n в N, которая определяется как
Операция т позволяет вводить в вычисления перебор объектов для отыскания нужного в бесконечном семействе.
Теперь, когда введены простейшие функции и элементарные операции, можно дать следующие основные определения:
а) последовательность частичных функций fi, . . . ,fN называют частично рекурсивным (соответственно примитивно рекурсивным) описанием функции fN = f, если fi - одна из простейших функций; fi для всех i ³ 2 либо является простейшей функцией, либо получается применением одной из элементарных операций к некоторым из функций fi,..., fi-1 (соответственно одной из элементарных операций, кроме т);
б) функция f называется частично рекурсивной (соответственно примитивно рекурсивной), если она допускает частично рекурсивное (соответственно примитивно рекурсивное) описание.
Теперь можно привести тезис Черча в обычной форме:
а) функция f полувычислима, если и только если она частично рекурсивна;
б) функция f вычислима, если и только если рекурсивны f и характеристическая функция XD(f).
Характеристическая функция подмножества Х в Y(XÌY) есть такая функция, что
Тезис Черча может использоваться как определение алгоритмической неразрешимости.
Пусть имеется счетная последовательность «задач» P1, P2, ..., которые имеют ответ «да» или «нет». Такая последовательность носит название «массовой проблемы». Свяжем с ней функцию
f из NвN:
Массовая проблема Р называется алгоритмически разрешимой, если функции f и XD(f) частично рекурсивны. В противном случае Р называется алгоритмически неразрешимой.
Контрольные вопросы и задания
1. Для чего необходимо формализовать понятие алгоритма?
2. Что означает фраза: «Машины Поста и Тьюринга являются абстрактными машинами»?
3. Для чего предназначены машины Поста и Тьюринга?
4. Как «устроена» машина Поста?
5. Перечислите и запишите команды машины Поста.
6. С помощью бумаги, карандаша и стиральной резинки «исполните» вместо машины Поста программы сложения чисел из текста.
7. Составьте (и проверьте) программу для машины Поста, создающую на ленте копию заданной последовательности меток справа от нее.
8. Пользуясь предыдущей программой, составьте программу умножения чисел для машины Поста.
9. Как «устроена» машина Тьюринга?
10. Каков принцип исполнения программы машиной Тьюринга?
11. Сравните машины Поста и Тьюринга. Укажите различия.
12. Выполните вместо машины Тьюринга примеры программ из текста.
13. Каким образом могут быть обобщена машина Тьюринга?
14. Что такое ассоциативное исчисление?
15. Постройте дедуктивную цепочку от слова «мука» к слову «торт», заменяя каждый раз по одной букве так, чтобы каждый раз получалось слово.
16. Дайте определение нормального алгоритма Маркова.
17. В чем состоит принцип нормализации алгоритмов?
18. Охарактеризуйте способы композиции нормальных алгоритмов.
19. Как алгоритм может быть связан с рекурсивной функцией?
20. Дайте определения частичной, полувычислимой и вычислимой функции.
21. В чем состоит тезис Черча в слабейшей и в обычной формах?
22. Перечислите простейшие функции.
23. Перечислите элементарные операции.
24. Чем отличается рекурсивная функция от примитивно-рекурсивной?
25. Дайте определение частично-рекурсивной функции.
26. Что называется массовой проблемой? Что означает алгоритмическая разрешимость массовой проблемы?