Машина Тьюринга:Унарное сложение — различия между версиями
Материал из CustisWiki
BenderBot (обсуждение | вклад) м (реплицировано из внутренней CustisWiki) |
StasFomin (обсуждение | вклад) (→Табличное представление МТ) |
||
Строка 3: | Строка 3: | ||
== Табличное представление МТ == | == Табличное представление МТ == | ||
− | + | <latex> | |
+ | \begin{tabular}{|cc|c|ccc|} | ||
+ | \hline | ||
+ | |||
+ | <\textcolor{blue}{1pass}> & * & $\Rightarrow$ & 2pass & 1 & R \\ \hline | ||
+ | <\textcolor{blue}{1pass}> & 1 & $\Rightarrow$ & <\textcolor{blue}{1pass}> & 1 & R \\ \hline | ||
+ | 2pass & * & $\Rightarrow$ & del1 & * & L \\ \hline | ||
+ | 2pass & 1 & $\Rightarrow$ & 2pass & 1 & R \\ \hline | ||
+ | del1 & 1 & $\Rightarrow$ & del2 & * & L \\ \hline | ||
+ | del2 & 1 & $\Rightarrow$ & rewind & * & L \\ \hline | ||
+ | rewind & * & $\Rightarrow$ & [\textcolor{red}{q}] & * & R \\ \hline | ||
+ | rewind & 1 & $\Rightarrow$ & rewind & 1 & L \\ \hline | ||
+ | \end{tabular} | ||
+ | </latex> | ||
<code-python> | <code-python> | ||
MT={ | MT={ |
Версия 17:42, 5 марта 2007
Приведем пример машины Тьюринга, выполняющей унарное сложение двух операндов. Операнды представляются в унарной системе, т. к. целое неотрицательное число n представляется n+1 единицей.
Содержание
Табличное представление МТ
MT={ 'k':1, 'start': '1pass', 'stop': 'q', 'program': { #(Состояние, символы на лентах) -> (новое состояние, (действия по каждой ленте)) ('1pass', ('1')): ('1pass', (('1','R'))), # проходим первое число ('1pass', ('*')): ('2pass', (('1','R'))), # меняем разделитель ('2pass', ('1')): ('2pass', (('1','R'))), # проходим второе число ('2pass', ('*')): ('del1', (('*','L'))), # конец второго числа ('del1', ('1')): ('del2', (('*','L'))), # удаляем первую лишнюю 1 ('del2', ('1')): ('rewind',(('*','L'))), # удаляем вторую лишнюю 1 ('rewind',('1')): ('rewind',(('1','L'))), # перематываем к началу. ('rewind',('*')): ('q', (('*','R'))) # конец. } }
Графовое представление МТ
Примеры выполнения МТ
«1» + «1»
«111» + «1»
«11» + «111»
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
Репликация: База Знаний «Заказных Информ Систем» → «Машина Тьюринга:Унарное сложение»