TA_lec2
Многоленточные машины Тьюринга Вычислительная способность многоленточных машин совершенно не превосходит их одноленточных аналогов. Задачи, которые можно решить на многоленточной машине с произвольным количеством лент, всегда решаются и при помощи одноленточной машины. Многоленточная машина для каждой ленты в общем случае может иметь свой внешний алфавит. Ленты в машине движутся независимо друг от друга. Состояние у машины единое, к лентам отношения не имеет - по сути, это состояние управляющего механизма. наглядно представить перемещение единого управляющего механизма по разным направлениям весьма проблематично, поэтому часто полагают, что именно ленты движутся относительно механизма Классический формат записи работы многоленточной машины Тьюринга: Si{a,b,c}→{a',b',c'}{R,L,H}Sj. Машина В эквивалентна машине А, если в соответствующие такты их работы лента машины В содержит всю информацию о ленте машины А. Примечание. Одна из машин может работать гораздо медленнее другой, т.к. каждый такт она моделирует несколькими тактами, поэтому мы говорим о соответствующих тактах. Если в конце концов А остановится, то В тоже остановится и к этому моменту будет содержать всю информацию о ленте машины А.