Добавил:

CanyonE СПбГУТ * ИКСС * Программная инженерия Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Санкт-Петербургский государственный университет телекоммуникаций им. проф. М.А. Бонч-Бруевича

Предмет:

Математическая логика и теория алгоритмов

Файл:

МЛиТА. Работа №3. 10 вариант

.pdf

Скачиваний:

Добавлен:

22.07.2020

Размер:

304.54 Кб

Скачать

☆

МАТЕМАТИЧЕСКАЯ ЛОГИКА. РАБОТА №3.

10 вариант. Коваленко Леонид. ИКПИ-81.

А)

( , ) = ( + 1)

( + 2)

: доказать, что функция

— ПРФ.

Б)

: найти

местную функцию

с помощью заданного

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

(

+ 1)

= 1, ( ) = 2 , ( , , )

= + 2 +

В)

34 , если 4

: доказать, что функция

— частично рекурсивная

функция, используя оператор минимизации.

Г)

( ) = 3 ÷ 4 =

неопределена, если

: построить машину Тьюринга, вычисляющую данную функцию в заданном

внешнем алфавите A, причем символ пустой клетки —

, и стоп-состояние .

Д)

( ) = 3 + 1, :

{0, 1,

в слово .

— дорога, — тропка: составить схему нормального алгоритма

, переводящего слово

Алфавит — русские буквы.

Решение.

( , )

= ( + 1)

А)

— ПРФ

( + 2)

( , + 1) = (

+ 1) (

( , 0)

= ( ) = 2 + 2

( + 1) = ( , )

+ + 1

— ПРФ

+ 2 + 1) = ( +

( + 2) +

( , ) = , − 1, ( , −

1) = + 1 + ( , − 1) =

= + 1 + + 1 + + 1 + 2 + 2 = ( + 1) +

2( + 1)

( + 1)( + 2)

( +1)

— ПРФ,

так как получается по схеме ПР:

( , )

= 1, ( )

= 2 + 2

, , ( , ) = + 1 + ( , )

Б)

( , ) =

+ 1 + ( , −

= 1, ( )

= 2 , ( , , ) = + 2 +

( , 0)

= ( )

= 2

( , )

( , + 1) = , ,

( , ) = + 2 + ( , )

1) =

= , − 1, ( , − 1) = + 2( − 1)

+ ( , −

= + 2( − 1)

+ + 2( − 2)

+ + 2(

− 3)

+ + 2

= + + +

+ 2 + 2 + 2 + + 2 + (−2 − 4 − − 2 )

=( )

=(2)

2(−2)−2( −1)

= ( ) + 2 + (2 )

+ (−1 −

) = ( + 2) + 2 2 −

= (2−1− )

− 2

(

+ 2) + ( − 1)

( , 1) = 3 ,

( , ) = ( + ) + ( − )

( , 4) = 6 + 12 …

В)

( , 2) = 4 + 2,

( ,

= 5 + 6,

( ) = 3 ÷ 4 =

3 , если 3

делитсяна4 безостатка

— ПРФ

неопределена, если 3 делитсяна 4 состатком

( , ) = |3 − 4 3| , если

кратно 4

не определена, если

делится на 4 с остатком

и( , )

= 3

÷ 4 = ( )

Действительно, если

кратно 4, то = 3

—

наименьший корень уравнения

, так как

( , ) = 0

( ,

−

= 3 − 4

− 1 = 4 ≠ 0

( ,

−

= 3 − 4

− 2 = 8 ≠ 0

… … … … … … … … … … … … …

Если же делится на					с( , 0) = 3\| \| ≠ 0, если ≠ 0, иначе = 0 и
	3				4				0
Таким	3	( )			4	остатком, тогда			0	= {0, 1, 2, … } ( , )
Г) (простой вариант с							( , )
минимизации			не определен.
МТ:	образом, функция							является частично-рекурсивной.
МТ:								( ) = 3 + 1,			: {0, 1, 2, 0}
				троичной системой счисления)

=|34 = 0 |

=3 − 4 ≠ 0, т. е. оператор


Пример.																0
1. Проходит вправо до конца													числа		и	ещё на1одну клетку1										, которая1						становится0				текущей.
2.		Меняет значение текущей клетки с																	на 1.		, 1,2,0,0,1,2,2, 0, 0											}
															{ 0			, 0		, 0	, 1,2,0,0,1,2,2, 0, 0											}
																				1→			, 2,0,0,1,2,2, 0, 0}
															{ 0, 0, 0, 1								, 2,0,0,1,2,2, 0, 0}
																				1→
															{ 0			, 0			… … … ….								, 0, 0			}
															{ 0			, 0		, 0,1,2,0,0,1,2, 2									, 0, 0			}
																									1→
																{ 0, 0, 0,1,2,0,0,1,2,2, 0 , 0}

																															}
																{ 0, 0, 0,1,2,0,0,1,2,2, 1 , 0															}
															( )			= 3 + 1,							: {0, 1, 2, 3, 0}
Г*) (дополнительное новое задание с 4-ричной системой счисления0																																)
( ) = 4 − + 1 =								( 1) + 1 −																										).
где			— битовый сдвиг влево в 4-ричной системе счисления.																															).
Для того, чтобы найти												(1234 1 = 12304)													(2710				1 = 10810)
Битовый сдвиг влево в 4-ричной системе счисления означает умножение числа на 4:
вычислить разность									( )		нужно добавить 1 в конец числа (т. е. произвести сдвиг единицы) и
Пример для проверки: (116											996.			37910		310				+ 110			= 350 989 13810)										(12		332 103 210 1234 34					+
14							получившегося числа и исходного.
14	= 110 322 322 231 1024)
МТ:
															2						1							1					1			1
														0	8						2							3					4			5
														0	0						7							6					6			6
														0	0						7							7					6			6
														0	0						7							7					7			6
														0	0						2							2					2			2
														0	0						2							2					2			2
Что делает МТ:														0	0					0		8						0					0			0
Что делает МТ:														0	0					0		8						0					0			0
1. Проходит вправо до конца и добавляет 1 в конец.
2.		Производит разность справа налево нетривиальным образом:
3.											13 (+1)						131 (1-3=-2)								132					122 (2-1=1)					112.
		После того, как достигнут левый													→					≠ 0				→			→							→
		Останавливается на первой цифре числа																			(слева).
Как работает на простых примерах:
	Вход			0	0			0		0	0					0			0			0		0						0	0				0		0	0		0
				0		0← 1				0	0						0		0	1→	0			0						0	0 1→				0		0	0	1→	0
					2→															← 1												1→							1→
				0		0 8				0	0						0		0 2→					0						0		0		←01			0	0	←01

	{ 0, 0	, 1	, 0	, 0}	0	0		←3		0		0	0	←2				0	0	2→
		0			0	0 ←6				0		0	0 2→					0	0	←3
					0	0				0		0	0	←3				0	0	←6
						2→								←3						←6
					0	0 8				0		0	0 ←7					0	0 2→
					0	0	0			0		0	0					0	0	←5
							0						2→							←5
												0	0 8→					0	0 ←7
												0	0	0	8			0	0
															8				2→
												0	0	0 0				0	0 8
																		0	0	0
Выход	0 0		0	0	0	0				0		0	0	0	4			0	0	0
	4			4	4					4		4			4			4		4
	Вход		(12 332 103 210 1234					34		+ 14	=	110 322 322 231 1024)
Как работает на сложном примере:

								0	0						0		0
							0		0 1→… (проход вправо) …							0	0
									0 1→… (проход вправо) …							0	0
							0		0						1→	0	0
								0	0						←01		0
							0		0						2→		0
								0	0						←5		0
							0		0						←7		0
							0		0						2→		0
							0		0						←4		0
							0		0						←6		0
							0		0					2→			0
							0		0						←3		0
							0		0					←6			0
							0		0				←2				0
							0		0				2→				0
							0		0				←3				0
							0		0				←7				0
							0		0			2→					0

	0	0			←4	0
	0	0			←7	0
	0	0			2→	0
	0	0			←5	0
	0	0			←7	0
	0	0		←2		0
	0	0		2→		0
	0	0		←3		0
	0	0		←7		0
	0	0		2→		0
	0	0		←4		0
	0	0		←7		0
	0	0	2→			0
	0	0		←5		0
	0	0	←7			0
	0	0	2→			0
	0	0	←5			0
	0	0	←7			0
	0	0	2→			0
	0	0	←4			0
	0	0	←6			0
	0	0 2→				0
	0	0	←3			0
	0	0 ←6				0
	0		0			0
		2→
	0	0 8				0
	0	0 0				0
Выход		0	0	4	4	0
			4	4	4	4

алфавит

Д) — дорога, — тропка. Введем

д :

{оа, г,рд,

к, о,

п, р

ат}

р о

д → т:

торога

о → а: тарага

р → о: таоага

а →∙ р: троага

а →∙ п: тропга

г →∙к: тропка

(дорога)

= тропка

Доказать,что

( ) = ÷ =

− , >

— частично-рекурсивная функция.

неопределена, <

Вспомним, что функции: −̇=

− , если

≥ , и + — ПРФ.

Рассмотрим функцию:

0, если <

. Эта функция естьПРФкак сумма двух ПРФ.

Тогдавведёмфункцию: ( , ) =

| − | = (−̇) + (−̇)

( , )

= |3 −( + 7)|

Тогда ( ) = 3 ÷ 7 = ( ) =

3 −7,3 > 7

— которая,очевидно, тоже ПРФ.

Действительно,уравнение

неопределена, 3 < 7

|3 −7 − | = 0

> 7

( , ) = 0

= 3

−7

— это уравнение

Если

, то корень

( ,

−1) =

|3 −7 −(3 −7 −1)| = 1 ≠ 0

— наименьший корень этого уравнения, так как:

( ,

−2) = |3 −7 −(3 −7 −2)| = 2 ≠ 0

: 3 ≠ 7

( , 0) = |3 −7 −0| =

|3 −

7| ≠ 0,

…

Таким

3 < 7

, то

= {0, 1, 2, … } |3 −7 − | ≠

, то естьоператор

( )

неопределен.

Если же

( )

образоммы доказали, что

полученаоператором минимизацииизПРФ, и поэтому является

частично-рекурсивной функцией.

3−̇(7 + )

+ (7 + )−̇3 = (7 + )−̇3

Для 3 < 7:

|3 −7 − | = |3 −(7 + )| =

Комментарий.

3 <7,≥0

Для

3 < 7

, то есть

то есть0

для

: (7 + )−̇3 ≠ 0

. То есть

7 −6 =

при

= 0

, но

= −1

мысделать не можем (

= 2: 0

. То есть

при

, но

). То есть оператор

( )

мысделать не можем (

неопределен.

7 −3 =

= 0

= −4

= 1: 0

: (7 + )−̇3 ≠ 0

. То есть

при

мысделать не можем(

( )

, но

для

). То естьоператор

неопределен.

7 −0 = 7

= 0

= −7

= 0: 0

: (7 + )−̇3 ≠ 0

( )

для

). То естьоператор

неопределен.

Соседние файлы в предмете Математическая логика и теория алгоритмов

#
16.06.2020349.33 Кб97Красовская Т. Ф. Основы теории алгоритмов.pdf
#
24.11.202059.41 Кб18Математическая логика и Бог в противоположность.pdf
#
22.07.2020157.11 Кб81МЛиТА. Работа №2. 10 вариант.pdf
#
22.07.2020304.54 Кб86МЛиТА. Работа №3. 10 вариант.pdf
#
17.12.2021190.09 Кб15МЛиТА. Тестирование остаточных знаний.pdf