304
правки
Изменения
→Варианты машины Тьюринга: добавлены варианты
== Варианты машины Тьюринга ==
В этом разделе приведены различные варианты машин Тьюринга, которые не отличаются от обычных машин Тьюринга по вычислительной мощности. === Многодорожечная машина Тьюринга ===Машиной Тьюринга с <tex>n</tex> дорожками называется вычислитель, аналогичный машине Тьюринга, лишь с тем отличием, что в каждой ячейке может быть записан не один, а <tex>n</tex> символов. Соответственно, функция перехода имеет тип <tex>\delta : Q \times \Pi^n \to Q \times \Pi^n \times \{\leftarrow, \rightarrow, \downarrow\}</tex>. Многодорожечная машина Тьюринга тривиально эквивалентна обычной с ленточным алфавитом <tex>\Pi' = \Pi^n</tex>.
=== Машина Тьюринга с полубесконечной лентой ===
Заменив у машины Тьюринга бесконечную в обе стороны ленту на бесконечную в одну сторону, мы не теряем в вычислительной мощности. По произвольной машине Тьюринга строится двухдорожечная машина с полубесконечной лентой следующим образом: в первой ячейке записывается символ <tex>\mathbb T</tex> (подразумевается, что он не является ленточным символом исходной машины), который сигнализирует о том, что нужно перейти с дорожки на дорожку и двигаться в обратном направлении. Это реализуется с помощью создания копий всех состояний исходного автомата, при этом правила для копии используют для чтения и записи вторую ленту и перемещают головку в противоположном направлении.
