Соглашения для сокращения записи
Договоримся о некоторых соглашениях, сокращающих запись программы для МТ.
1) Если в такте не меняется видимый символ, или автомат не сдвигается, или не меняется состояние автомата, то в соответствующей позиции такта мы не будем ничего писать.
Например, при конфигурации <a, q1> следующие записи тактов эквивалентны:
Замечание. Запятые в тактах желательно не опускать, т.к. иначе возможна путаница, если среди символов на ленте могут встретиться буквы L и R.
2) Если надо указать, что после выполнения некоторого такта МТ должна остановиться, то в третьей позиции этого такта будем писать знак «!». Например, такт b,L,! означает следующие действия: запись символа b в видимую клетку ленты, сдвиг влево и останов.
Формально можно считать, что в программе МТ имеется состояние с названием ! , во всех ячейках которого записаны такты останова. При этом, однако, такую строку явно не выписывают, а лишь подразумевают.
3) Если заранее известно, что в процессе выполнения программы не может появиться некоторая конфигурация, тогда, чтобы подчеркнуть это явно, будем в соответствующей ячейке таблицы рисовать крестик. (Формально этот крестик считается тактом останова.)
Эти соглашения необязательны, но они сокращают запись программы и упрощают ее восприятие.
Достарыңызбен бөлісу: |
