Задание (стр. 3 )

A) C(x, y) = (x+y)(x+y+1)/2 + x

B) C(x, y) = (x+y)(x+y+1) + x

C) C(x, y) = (x+y)(x+y+1)/2 + y

D) C(x, y) = (x+y)(x+y+1)/3 + x

E) C(x,y) = (x+y)(x+y+2)/2 + x

*****

Какую функцию f(x) вычисляет машина Т со следующей программой команд: ?

A) f(x) = x+2

B) f(x) = x

C) f(x) = x+1

D) f(x) = 0

E) f(x) = 1

*****

Какую функцию f(x) вычисляет машина Т со следующей программой команд: ?

A) f(x) = x+2

B) f(x) = x

C) f(x) = x+1

D) f(x) = 0

E) f(x) = 1

*****

Укажите машину Тьюринга, которая вычисляет функцию f(x) = x+1?

A)

B)

C)

D)

E)

*****

Укажите машину Тьюринга, которая вычисляет функцию f(x) = x?

A)

B)

C)

D)

E)

*****

Какую функцию f(x,y) вычисляет машина Т со следующей программой команд: ?

A) f(x, y) = x+y+2

B) f(x, y) = x+y

C) f(x, y) = xy

D) f(x, y) = x-y

E) f(x,y) = x+y+1

*****

Какую функцию f(x,y,z) вычисляет машина Т со следующей программой команд: ?

A) f(x, y,z) = x+y+z+2

B) f(x, y,z) = x+y+z

C) f(x, y,z) = xyz

D) f(x, y,z) = x-y-z

E) f(x,y,z) = x+y+z+1

*****

Укажите машину Тьюринга, которая правильно вычисляет функцию f(x) = 0?

A)

B)

C)

D)

E)

*****

Укажите машину Тьюринга, которая правильно вычисляет функцию f(x) = x+1?

A)

B)

C)

D)

E)

*****

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

A) f(x) = x+2

B) f(x) = x

C) f(x) = x+1

D) f(x) = 0

E) f(x) = 1

*****

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

A) f(x) = x+2

B) f(x) = x

C) f(x) = x+1

D) f(x) = 0

E) f(x) = 1

*****

Сформулируйте принцип нормализации Маркова.

A) Частичная числовая функция является вычислимой тогда и только тогда, когда она является частично рекурсивной.

B) Частичная числовая функция является вычислимой тогда и только тогда, когда она является вычислимой по Тьюрингу.

C) Частичная числовая функция является вычислимой тогда и только тогда, когда она является примитивно рекурсивной.

D) Частичная числовая функция является вычислимой тогда и только тогда, когда она является нормально вычислимой.

E) Частичная числовая функция является вычислимой тогда и только тогда, когда она является общерекурсивной.

*****

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

A) f(x) = x+2

B) f(x) = x

C) f(x) = x+1

D) f(x) = x+y

E) f(x) = 1

*****

Найдите номер тройки (3, 0, 4).

A) 100

B) 259

C) 160

D) 157

E) 148

*****

Частичная функ­ция называется частично рекурсивной относительно системы частичных функций , если

A) может быть полу­чена из функций системы и простейших функций конечным числом операций подстановки, примитивной рекурсии и минимизации

B) может быть полу­чена из функций системы конечным числом операций подстановки, примитивной рекурсии и минимизации

C) может быть полу­чена из функций системы и простейших функций конечным числом операций подстановки, примитивной рекурсии

D) может быть полу­чена из функций системы и простейших функций конечным числом операций примитивной рекурсии и минимизации

E) может быть полу­чена из простейших функций конечным числом операций подстановки, рекурсии и минимизации

*****

Говорят, что n-местная функция f получается из n-местной функции g операцией суммирования, если

A)

B)

C)

D)

E)

*****

Говорят, что n-местная функция f получается из n-местной функции g операцией мультиплицирования, если

A)

B)

C)

D)

E)

*****

Укажите, почему нельзя доказать тезис Тьюринга

A) в нем употребляется нестрогое понятие вычислимой функции

B) отсутствие достаточных математических знаний

C) в нем употребляется понятие числовой функции

D) в нем употребляется понятие рекурсивной функции

E) в нем употребляется понятие частично рекурсивной функции

*****

Укажите, что следует из определения машины Тьюринга (условие 3а))

A) машина Тьюринга М может переводить слово только в одно слово

B) машина Тьюринга М не может переводить слово ни в какое слово

C) слово является тупиковым

D) машина М может быть не применима к слову

E) если машинное слово содержит символ , то оно является тупиковым для М

*****

Укажите, что следует из определения машины Тьюринга (условие 3б))

A) машина Тьюринга М может переводить слово только в одно слово

B) машина Тьюринга М не может переводить слово ни в какое слово

C) слово является тупиковым

D) машина М может быть не применима к слову

E) если машинное слово содержит символ , то оно является тупиковым для М

*****

Укажите, с помощью, какой команды машина М переводит слово 0000 в слово а0000