Строение машины Тьюринга

91. Задание {{ 84 }} ТЗ 84 Тема 7-40-0

Каковы общие требования предъявляемые к алгоритмам?

£ Алгоритм должен быть: универсальным, конечным, сложным;

£ Алгоритм должен быть: универсальным, бесконечным, элементарным;

£ Алгоритм должен быть: индивидуальным, конечным, элементарным;

R Алгоритм должен быть: универсальным, конечным, элементарным.

92. Задание {{ 85 }} ТЗ 85 Тема 7-40-0

Из чего состоит всякая машина Тьюринга?

£ ленты, читающей головки, алфавита, внутреннего состояния;

£ читающей ленты, алфавита, внутреннего состояния, программы команд;

£ ленты, читающей головки, алфавита, внутреннего состояния, внешнего состояния;

R ленты, читающей головки, алфавита, внутреннего состояния, программы команд.

93. Задание {{ 86 }} ТЗ 86 Тема 7-40-0

Сколько символов можно вписывать в каждую ячейку ленты?

R один;

£ два;

£ три;

£ сколько угодно.

94. Задание {{ 87 }} ТЗ 87 Тема 7-40-0

За один такт работы машины Тьюринга читающая головка может передвигаться влево и воспринимать ...

£ соседнюю с верху ячейку;

£ соседнюю с права ячейку;

R соседнюю слева ячейку;

£ ту же ячейку.

95. Задание {{ 88 }} ТЗ 88 Тема 7-40-0

За один такт работы машины Тьюринга читающая головка может передвигаться вправо и воспринимать ...

£ соседнюю с верху ячейку;

R соседнюю с права ячейку;

£ соседнюю слева ячейку;

£ ту же ячейку.

96. Задание {{ 89 }} ТЗ 89 Тема 7-40-0

За один такт работы машины Тьюринга читающая головка может остаться на месте и воспринимать ...

£ соседнюю с верху ячейку;

£ соседнюю с права ячейку;

£ соседнюю слева ячейку;

R ту же ячейку.

97. Задание {{ 90 }} ТЗ 90 Тема 7-40-0

Какие операции над машинами Тьюринга мы можем проводить?

£ Произведение машин, произведение машин с разветвлением, сложение машин;

£ Произведение машин, произведение машин с разветвлением и циклом, сложение машин;

R Произведение машин, произведение машин с разветвлением, произведение машин с разветвлением и циклом;

£ Произведение машин, сложение машин, деление машин.

98. Задание {{ 309 }} ТЗ № 309

В каком случае, говорят, что машина Тьюринга стандартно воспринимает натуральное число ?

£ если обрабатываемая лента содержит единиц в одном из обрабатываемых лент;

R если обрабатываемая лента содержит единиц в одном из обрабатываемых лент;

£ если обрабатываемая лента содержит единиц в одном из обрабатываемых лент;

£ если обрабатываемая лента содержит единиц в одном из обрабатываемых лент.

99. Задание {{ 310 }} ТЗ № 310

Говорят, что машина Тьюринга стандартно воспринимает кортеж натуральных чисел , если обрабатываемая лента имеет вид:

£

£

£

R

100. Задание {{ 311 }} ТЗ № 311

Даны две машины и . Новая машина с начальным состоянием и конечным состоянием называется …

£ разветвлением и циклом машины на и .

£ разветвлением машины на и

R произведением машин и .

£ объединением машин и .