Основные понятия теории вычислимости и разрешимости. Способ вычисления функций с помощью машины Тьюринга. Конечные детерминированные полностью определённые одноленточные автоматы, алгоритм проверки эквивалентности. Стандартные, рекурсивные схемы программ.
Теория вычислительных процессовФункцией, отображающей множество Х во множество Y (обозначение F: X > Y), называется множество F I X?Y такое, что для любых пар (x, y)IF и (x’ y’)I F из x = x’ следует, что y = y’. Словом в алфавите V называется конечный объект, получаемый выписыванием одного за другим символов V, например, а 1 = 1 а - слово в алфавите V3, 101011 - слово в алфавите V2, abaab - слово в алфавите V1. Множество всех слов в алфавите V обозначается V*. n-местной словарной функцией над алфавитом V называют n-местную функцию над V, т. е. функцию из V ? V ? … ? V (n раз) в V*. Если машина не останавливается, начав работу с некоторым словом на ленте, то функция, задаваемая машиной, считается неопределенной для этого слова. Пусть М - множество всех пар слов в алфавите V, в каждой паре первое слово - словарное представление некоторой машины Тьюринга, второе - такое слово, что эта машина останавливается, начав работу над ним.
План
Оглавление
Лабораторная работа 1. Вычислимость и разрешимость
Лабораторная работа 2. Конечные детерминированные полностью определенные одноленточные автоматы
Лабораторная работа 3. Схемы программ
Лабораторная работа 4. Сети Петри
Рекомендуемая литература
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
