Дисциплина «Математическая логика и теория алгоритмов» (стр. 5 )

2.        Построить в алфавите машину Тьюринга, переводящую конфигурацию К1 в конфигурацию К0.

       1) ;        2) .

3.        Сконструируйте нормальные алгоритмы, вычисляющие функции:

       1) ;                        2) .

ВАРИАНТ 2

Выяснить, применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то найти результат применения машины Т к слову Р. Предполагается, что начальная и заключительные конфигурации имеют стандартную форму.

2.        Построить в алфавите машину Тьюринга, переводящую конфигурацию К1 в конфигурацию К0.

       1) ;        2) .

3.        Сконструируйте нормальные алгоритмы, вычисляющие функции:

       1) ;                        2) .

Задачи для проверки остаточных знаний

Примитивно рекурсивные функции, отношения и предикаты

Докажите, что следующие функции примитивно рекурсивны:

1);        2);                3);                

4)        5);                        6).

Докажите, что следующие функции примитивно рекурсивны:

1);                2);                3).

Докажите, что следующие функции примитивно рекурсивны:

1)   – остаток от деления на ();

2) – число делителей числа ();

3) – сумма делителей числа ().

Определите последовательности, заданные по схеме рекурсии

1);        2) ;        3) ;

4) ;        5);        6).

Предикаты P(x) и Q(x) примитивно рекурсивны. Определим: (P?Q)(x)?P(x)?Q(x) для всех x?N, где логическая связка ? задана следующей таблицей истинности:

P	Q	P?Q
И	И	Л
И	Л	И
Л	И	И
Л	Л	И

Докажите, что предикат (P?Q)(x) тоже примитивно рекурсивный.

Предикаты P(x) и Q(x) примитивно рекурсивны. Определим: (P?Q)(x)?P(x)?Q(x) для всех x?N, где логическая связка ? задана следующей таблицей истинности:

P	Q	P?Q
И	И	Л
И	Л	И
Л	И	И
Л	Л	Л

Докажите, что предикат (P?Q)(x) тоже примитивно рекурсивный.

Функция y=f(x) определена «с перебором случаев»:

Докажите, что функция y=f(x) примитивно рекурсивная.

Пусть f – примитивно рекурсивная n-местная функция, а n-местная функция g, такая, что ?x1,x2,…,xn?Ng(x1,x2,x3,…,xn)=f(x2,x1,x3,…,xn). Докажите, что функция g примитивно рекурсивная (n?2). Пусть f – примитивно рекурсивная n-местная функция, а (n?1)-местная функция g, такая, что ?x1, x2,…, xn?1?Ng(x1, x2,…, xn?1)=f(x1, x1, x2,…, xn-1). Докажите, что функция g примитивно рекурсивная. Пусть f – примитивно рекурсивная 3-местная функция, а 5-местная функция g, такая, что ?x1, x2, x3, x4, x5?Ng(x1, x2, x3, x4, x5)=f(x2, x3, x4). Докажите, что функция g примитивно рекурсивная. Пусть f – примитивно рекурсивная 6-местная функция, а 3-местная функция g, такая, что ?x1, x2, x3?Ng(x1, x2, x3)=f(x2, x3, x2, x3, x2, x3). Докажите, что функция g примитивно рекурсивная.

Машина Тьюринга

Выяснить, применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то найти результат применения машины Т к слову Р. Предполагается, что начальная и заключительные конфигурации имеют стандартную форму.

Постройте машину Тьюринга, преобразующую машинное слово q101x0010 в машинное слово 01x011q00 (x>0). Постройте машину Тьюринга, преобразующую машинное слово q1001x+10 в машинное слово 0101xq00 (x>0). Постройте машину Тьюринга, преобразующую машинное слово 01x011q10 в машинное слово q001x0010 (x>0). Постройте машину Тьюринга, преобразующую машинное слово q10001x0 в машинное слово 0101xq00 (x>0). Постройте машину Тьюринга, преобразующую машинное слово q101x00101y0 в машинное слово 00100x01yq00 (x, y>0).

Тесты текущего контроля по дисциплине «Математическая логика и теория алгоритмов»

Дополнение к области определения некоторой вычислимой функции _________ рекурсивно перечислимым 

A)        может не быть;

B)        разъединено с ;

не может быть;

D)        должно быть.

Множество ________ тогда и только тогда, когда оно является _______ некоторой вычислимой функции

A)        перечислимо, множеством значений;

B)        разрешимо, множеством значений;

разрешимо, областью определения;

D) перечислимо, областью определения.

Если и рекурсия проводится по , то функция

равна

0; ; x+z; . Функция, полученная из вычислимой с помощью рекурсии, является Вычислимой; примитивно рекурсивной; дифференцируемой; частично рекурсивной. Геделевский номер, равный , имеет функция ; ; ; . Показал возможность существования универсальной вычислительной машины, способной выполнить любую эффективную процедуру А. Тьюринг; Д. Гильберт; А. Марков; К. Гёдель. Машина Тьюринга есть совокупность компонент пяти; двух; четырех; трех. Множество натуральных чисел является только рекурсивным; только перечислимым; рекурсивным и перечислимым; простейшим. Формализованный язык для однозначной записи алгоритмов называется автоматным языком; регулярным языком; метаязыком языком; алгоритмическим языком. Если множество не является множеством значений никакой функции, то оно нерекурсивно, но рекурсивно перечислимо; рекурсивно, но не перечислимо; нерекурсивно и неперечислимо; рекурсивно, но не перечислимо.

11.        Усеченная разность равна