Составители:
Рубрика:
играет роль разделителя. Символы q , q
1 0
– соответственно начальное
и заключительное состояние машины (останов).
Рассматриваемые машины выполняют арифметичекие операции
над неотрицательными целыми числами, для представления которых
используется унитарнй код. Число x представляется (x+1)-й
единицей, причем отдельно записанная единица представляет
нулевое значение x.
Пример 4.1. Прибавление единицы. В
таблице 4.1 приведен пример программы
машины с алфавитом состояний {q
Таблица 4.1
1
,q
2
,q
0
}.
Машина увеличивает значение числа на
единицу.
Например, увеличение числа три на
единицу машина осуществляет за два шага:
…ΛΛq
1
1111Λ… ⇒ …Λq
2
Λ1111Λ… ⇒ …Λ q
0
11111Λ… .
Для исходной конфигурации …Λq
1
Λ11Λ… поведение машины не определено.
Это означает, что рассматриваемая машина реализует частичную словарную
функцию.
Пример 4.2. Усеченное вычитание
единицы. В таблице 4.2 приведен пример
программы машины, выполняющей усеченное
вычитание единицы. Вычитание единицы для
неотрицательных целых чисел – частичная
функция, поскольку значение 0-1 не
определено. Введем усеченное вычитание ¬,
доопределив обычное вычитание: x¬y = x-y
для x≥y и x¬y =0 для x < y.
Например, усеченное вычитание единицы из четырех машина
осуществляет за два шага:
…Λq
1
11111Λ… ⇒ …ΛΛq
2
1111Λ… ⇒ …ΛΛq
0
1111Λ… .
Усеченное вычитание из нуля:
…Λq
1
1ΛΛ… ⇒ …ΛΛq
2
ΛΛ… ⇒ …ΛΛq
0
1Λ… .
q a
q
q
1 2
-
Λ
1Нq
0
1 -
1Пq
2
Таблица 4.2
q a
q
q
1 2
Λ
1Нq
ΛНq
0 0
1
ΛПq
1Нq
2 0
146
Страницы
- « первая
- ‹ предыдущая
- …
- 60
- 61
- 62
- 63
- 64
- …
- следующая ›
- последняя »
