тест Машина Тьюринга

Тест «Машина Тьюринга»

В машине Тьюринга предписание L для лентопротяжного механизма означает:

Переместить ленту вправо

Переместить ленту влево

Остановить машину

Занести в ячейку символ

В машине Тьюринга предписание R для лентопротяжного механизма означает:

Переместить ленту вправо

Переместить ленту влево

Остановить машину

Занести в ячейку символ

В машине Тьюринга предписание S для лентопротяжного механизма означает:

Переместить ленту вправо

Переместить ленту влево

Остановить машину

Занести в ячейку символ

В машине Тьюринга рабочий алфавит:

А = {a40 0, b40 1, c40 2, … , w40 t};

А = {a40 0, a40 1, a40 2, … , a40 t};

А = {a40 0, a41 0, a42 0, … , a4t 0};

А = {a10 0, a20 0, a30 0, … , a90 0}

В машине Тьюринга состояниями являются:

{a40 0, a40 1,a402, …,a40 t};

{q41, q42, q43, …, q4s};

{q41, q42, q43, …, q4s, a40 0, a40 1, a40 2,…,a40 t};

{q40, q41, q42, …, q4s}.

Результат применения команды машины Тьюринга к машинному слову

Результат применения команды машины Тьюринга к машинному слову

Результат применения команды машины Тьюринга к машинному слову

2)

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

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

Машина Тьюринга задана функциональной схемой

Ответы на тест по машине тьюринга

В какое слово переработает машина слово , исходя из стандартного начального положения

0110 2)011110

01111 4)011100





Установите соответствие

а) пустая буква

1) q1

b) начальное состояние

2) q0

c) стоп-состояние

3) a1

4) a0

Конфигурация (машинное слово), соответствующая изображению

Ответы на тест по машине тьюринга

Если значение вычислимой по Тьюрингу функции f(x1, …, xn) не определено, то …

Машина останавливается через конечное число шагов, на ленте записано пустое слово

Машина останавливается через конечное число шагов, на ленте записано исходное слово

Машина останавливается через конечное число шагов, на ленте записано слово «error»

Машина работает бесконечно

Функция f(x1, x2) является вычислимой по Тьюрингу. Для вычисления значения f(1,3) начальная конфигурация имеет вид

0101110

010111q10

1*111

1*11q11

Функция f(x) является вычислимой по Тьюрингу. Машина Тьюринга, вычисляющая ее значения, задана функциональной схемой

Ответы на тест по машине тьюринга

Формульное выражение функции f(x) имеет вид

Функция f(x) является вычислимой по Тьюрингу. Машина Тьюринга, вычисляющая ее значения, задана функциональной схемой

Значение функции f(2) равно …

Функция f(x) является вычислимой по Тьюрингу. Машина Тьюринга, вычисляющая ее значения, задана функциональной схемой

Значение функции f(2) равно …

Функция f(x) является вычислимой по Тьюрингу. Машина Тьюринга, вычисляющая ее значения, задана функциональной схемой

Значение функции f(0) равно …

Функция f(x) является вычислимой по Тьюрингу. Машина Тьюринга, вычисляющая ее значения, задана функциональной схемой