ВУЗ:
Составители:
Рубрика:
61
1) Начав работу с первой единицы массива из единиц, машина “сдвигает” его на две
ячейки вправо, не изменяя остального содержимого ленты, и останавливается на
последней единице перенесенного массива.
2)
Начав двигаться влево от произвольной ячейки, головка находит первую при
таком перемещении ячейку с единицей (если такая встретится на пути) и, сделав
один шаг вправо, останавливается на соседней ячейке. Содержимое ленты не
меняется.
3)
Машина начинает работу с самой левой непустой ячейки и отыскивает нуль,
примыкающий с левой стороны к первому справа массиву из трех единиц,
окаймленному нулями. Головка останавливается на первой единице найденного
массива (если такой есть). Содержимое ленты не меняется.
4)
Головка машины, начав работу с произвольной ячейки, содержащей единицу,
двигается влево до тех пор, пока не пройдет подряд пять нулей. Головка
останавливается на первой ячейке слева за этими пятью нулями, напечатав в ней
единицу. Остальное содержимое ленты не меняется.
5)
При заданном 1≥n головка машины, начав работу с произвольной ячейки и
двигаясь вправо, записывает подряд n2 нулей и останавливается на последнем из
них.
6)
Головка машины, двигаясь вправо от какой-либо пустой ячейки, находит первый
при таком перемещении массив, содержащий не менее семи единиц, стирает в
нем первые семь единиц и останавливается на самой правой из ячеек, в которых
были стерты единицы. Остальное содержимое ленты не меняется.
7)
При заданном значении n головка машины из n записанных единиц оставляет на
ленте 2−n единицы, так же записанных подряд, если 2≥n , и работает вечно,
если 0=n или 1
=
n .
8)
Машина реализует алгоритм вычисления функции 0)(
=
n
ϕ
, считая, что число n
представляется записанными подряд n единицами, и массив из n единиц уже
найден.
9)
Машина реализует алгоритм вычисления функции 1)(
=
n
ϕ
, считая, что число n
представляется записанными подряд n единицами, и массив из n единиц уже
найден.
10)
Машина реализует алгоритм вычисления функции
⎩
⎨
⎧
=
.на делитсянеесли ,0
,наделитсяесли ,1
)(
pn
pn
nf
p
Считается, что число n представляется записанными подряд n единицами, и
массив из n единиц уже найден.
11)
Показать, что для всякой машины Тьюринга существует эквивалентная ей
машина, в программе которой отсутствуют заключительные состояния.
12)
Показать, что для всякой машины Тьюринга существует эквивалентная ей
машина, в программе которой отсутствует символ E.
5. Для машин Тьюринга из задачи 1 построить двойственные машины.
1) Начав работу с первой единицы массива из единиц, машина “сдвигает” его на две
ячейки вправо, не изменяя остального содержимого ленты, и останавливается на
последней единице перенесенного массива.
2) Начав двигаться влево от произвольной ячейки, головка находит первую при
таком перемещении ячейку с единицей (если такая встретится на пути) и, сделав
один шаг вправо, останавливается на соседней ячейке. Содержимое ленты не
меняется.
3) Машина начинает работу с самой левой непустой ячейки и отыскивает нуль,
примыкающий с левой стороны к первому справа массиву из трех единиц,
окаймленному нулями. Головка останавливается на первой единице найденного
массива (если такой есть). Содержимое ленты не меняется.
4) Головка машины, начав работу с произвольной ячейки, содержащей единицу,
двигается влево до тех пор, пока не пройдет подряд пять нулей. Головка
останавливается на первой ячейке слева за этими пятью нулями, напечатав в ней
единицу. Остальное содержимое ленты не меняется.
5) При заданном n ≥ 1 головка машины, начав работу с произвольной ячейки и
двигаясь вправо, записывает подряд 2n нулей и останавливается на последнем из
них.
6) Головка машины, двигаясь вправо от какой-либо пустой ячейки, находит первый
при таком перемещении массив, содержащий не менее семи единиц, стирает в
нем первые семь единиц и останавливается на самой правой из ячеек, в которых
были стерты единицы. Остальное содержимое ленты не меняется.
7) При заданном значении n головка машины из n записанных единиц оставляет на
ленте n − 2 единицы, так же записанных подряд, если n ≥ 2 , и работает вечно,
если n = 0 или n = 1 .
8) Машина реализует алгоритм вычисления функции ϕ (n) = 0 , считая, что число n
представляется записанными подряд n единицами, и массив из n единиц уже
найден.
9) Машина реализует алгоритм вычисления функции ϕ (n) = 1 , считая, что число n
представляется записанными подряд n единицами, и массив из n единиц уже
найден.
10) Машина реализует алгоритм вычисления функции
⎧1, если n делится на p,
f p ( n) = ⎨
⎩0, если n не делится на p.
Считается, что число n представляется записанными подряд n единицами, и
массив из n единиц уже найден.
11) Показать, что для всякой машины Тьюринга существует эквивалентная ей
машина, в программе которой отсутствуют заключительные состояния.
12) Показать, что для всякой машины Тьюринга существует эквивалентная ей
машина, в программе которой отсутствует символ E.
5. Для машин Тьюринга из задачи 1 построить двойственные машины.
61
