Машина Тьюринга - История изменений

StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»

2011-06-13T17:32:00Z

Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»

Внесённые изменения

WikiSysop: 1 версия

2008-10-23T16:48:12Z

1 версия

StasFomin: обновление данных

2008-10-22T15:34:19Z

обновление данных

WikiSysop: 1 версия

2008-08-04T09:55:52Z

1 версия

BenderBot: реплицировано из внутренней CustisWiki

2007-03-06T04:54:11Z

реплицировано из внутренней CustisWiki

Внесённые изменения

StasFomin: обновил табличное представление МТ

2007-03-05T13:46:30Z

обновил табличное представление МТ

BenderBot: реплицировано из внутренней CustisWiki

2005-12-08T04:41:56Z

реплицировано из внутренней CustisWiki

@@ Строка 4: / Строка 4: @@
 Ленты поделены на соответственно бесконечное число ячеек, и на каждой ленте
 выделена стартовая (нулевая) ячейка. В каждой ячейке может быть записан
-только один символ из некоторого конечного алфавита <math>\Sigma</math>, где
+только один символ из некоторого конечного алфавита <m>\Sigma</m>, где
 предусмотрен символ «*» для обозначения пустой ячейки.
 На каждой ленте имеется головка чтения-записи, и все они
-подсоединены к «управляющему модулю» МТ — автомату с конечным множеством состояний <math>\Gamma</math>.
+подсоединены к «управляющему модулю» МТ — автомату с конечным множеством состояний <m>\Gamma</m>.
 Имеется выделенное стартовое состояние (например, «START») и состояние (или набор состояний) завершения (например «STOP»).
@@ Строка 25: / Строка 25: @@
 ''Машина Тьюринга'' это набор
-<math>T= \langle k,\Sigma,\Gamma,\alpha,\beta,\gamma \rangle</math>,
+<m>T= \langle k,\Sigma,\Gamma,\alpha,\beta,\gamma \rangle</m>,
 где
 ;k: натуральное число,
-;<math>\Sigma,\Gamma</math>: конечные множества входного алфавита и состояний соответственно,
+;<m>\Sigma,\Gamma</m>: конечные множества входного алфавита и состояний соответственно,
-;<math>\star \in \Sigma</math>: символ-пробел,
+;<m>\star \in \Sigma</m>: символ-пробел,
-;<math>START,STOP \in \Gamma</math>: выделенные состояния,
+;<m>START,STOP \in \Gamma</m>: выделенные состояния,
-;<math>\alpha,\beta,\gamma</math>: произвольные отображения:
+;<m>\alpha,\beta,\gamma</m>: произвольные отображения:
-:*<math>\alpha: \Gamma \times \Sigma^k \rightarrow \Gamma  </math> (задает новое состояние);
+:*<m>\alpha: \Gamma \times \Sigma^k \rightarrow \Gamma  </m> (задает новое состояние);
-:*<math>\beta : \Gamma \times \Sigma^k \rightarrow \Sigma^k  </math> (задает символы для записи на ленты);
+:*<m>\beta : \Gamma \times \Sigma^k \rightarrow \Sigma^k  </m> (задает символы для записи на ленты);
-:*<math>\gamma: \Gamma \times \Sigma^k \rightarrow \{-1,0,1\}^k </math> (определяет, как двигать головки).
+:*<m>\gamma: \Gamma \times \Sigma^k \rightarrow \{-1,0,1\}^k </m> (определяет, как двигать головки).
-Удобно считать, что алфавит <math>\Sigma</math> содержит кроме «пробела» («*»)
+Удобно считать, что алфавит <m>\Sigma</m> содержит кроме «пробела» («*»)
-два выделенных символа, «0» и «1» (Обычно вовсе ограничиваются <math>\Sigma \equiv \{\star,0,1\}</math>).
+два выделенных символа, «0» и «1» (Обычно вовсе ограничиваются <m>\Sigma \equiv \{\star,0,1\}</m>).
-Под ''входом'' для МТ подразумевается набор из ''k'' слов (''k''-кортеж слов из <math>\Sigma^*</math>),
+Под ''входом'' для МТ подразумевается набор из ''k'' слов (''k''-кортеж слов из <m>\Sigma^*</m>),
 записанных на ''k'' лентах начиная с нулевых позиций.
 Обычно, на входные данные записывают только на первую ленту, и под входом ''x''
-подразумевают ''k''-кортеж <math>\langle x,0,\ldots,0 \rangle</math>.
+подразумевают ''k''-кортеж <m>\langle x,0,\ldots,0 \rangle</m>.
 {\it Результатом} работы МТ на некоем входе является также
-''k''-кортеж слов из <math>\Sigma^*</math>, оставшихся на лентах. Для простоты
+''k''-кортеж слов из <m>\Sigma^*</m>, оставшихся на лентах. Для простоты
 также удобно считать, что ''результатом'' является только слово на последней
 ленте, а все остальное — просто мусор.

← Предыдущая	Версия 09:55, 4 августа 2008
(не показана 1 промежуточная версия 1 участника)
(нет различий)

@@ Строка 62: / Строка 62: @@
 <code-python>
-def execute_MT(MT,Tape):
+def execute_MT(MT,input):
-    k=MT["k"]
      T=MT["program"]
-     Tape=["*"]+Tape[:]
+     tape=["*"]+input
-     configuration={"state":MT["start"], "position":1, "tape": Tape}
+    state=MT["start"]
-    history=[configuration]
+     position=1
      step=0
      while 1:
         step=step+1
-        #if we reach the end of the tape --- enlarge it
+        if position>=len(tape):
-       if configuration["position"]>=len(configuration["tape"]):
+            tape.append("*")
-            configuration["tape"].append("*")
+        symbol_under_head=tape[position]
+        action=T[(state,(symbol_under_head))]
-        #the symbol we are looking at
+        state=action[0]
-       symbol=configuration["tape"][configuration["position"]]
+        symbol_to_write=action[1][0]
+        tape[position]=symbol_to_write
-       #perform transition
-       key=(configuration["state"],(symbol))
-        action=T[key]
-−
-       # Just cloning entire configuration: (state,head position,tape)
-       new_tape=configuration["tape"][:]
-       new_configuration=dict(configuration)
-       new_configuration["tape"]=new_tape
-        configuration=new_configuration
-−
-       #changing state
-       configuration["state"]=action[0]
-−
-       #write new symbol
-       symbol=action[1][0]
-        configuration["tape"][configuration["position"]]=symbol
-−
-       #move head
         move=action[1][1]
-        if move=="L": configuration["position"]=configuration["position"]-1
+        if move=="L": position=position-1
-        if move=="R": configuration["position"]=configuration["position"]+1
+        if move=="R": position=position+1
+        history.append({"state":state, "position":position, "tape": []+tape})
-       #tracking configuration
+        if state==MT["stop"] or step>1000:
-        history.append(configuration)
-−
-       #if stop state - finishing
-       if configuration["state"]==MT["stop"] or step>1000:
             break
      return history
 </code-python>
@@ Строка 112: / Строка 89: @@
 Он принимает на вход описание машины Тьюринга в виде хэш-таблицы — рассмотрим пример машины тьюринга для задачи удвоения входной строки (алфавит состоит только из «1»).
-Описание соответствующей МТ:
+Табличное описание МТ:
 <code-python>
 MT={

@@ Строка 62: / Строка 62: @@
 <code-python>
-def execute_MT(MT,input):
+def execute_MT(MT,Tape):
      T=MT["program"]
-     tape=["*"]+input
+     Tape=["*"]+Tape[:]
-    state=MT["start"]
+     configuration={"state":MT["start"], "position":1, "tape": Tape}
-     position=1
+    history=[configuration]
-    history=[{"state":state, "position":position, "tape": []+tape}]
      step=0
      while 1:
         step=step+1
-        if position>=len(tape):
+        #if we reach the end of the tape --- enlarge it
-            tape.append("*")
+       if configuration["position"]>=len(configuration["tape"]):
-        symbol_under_head=tape[position]
+            configuration["tape"].append("*")
-        action=T[(state,(symbol_under_head))]
-        state=action[0]
+        #the symbol we are looking at
-        symbol_to_write=action[1][0]
+       symbol=configuration["tape"][configuration["position"]]
-        tape[position]=symbol_to_write
         move=action[1][1]
-        if move=="L": position=position-1
+        if move=="L": configuration["position"]=configuration["position"]-1
-        if move=="R": position=position+1
+        if move=="R": configuration["position"]=configuration["position"]+1
-        history.append({"state":state, "position":position, "tape": []+tape})
-        if state==MT["stop"] or step>1000:
+       #tracking configuration
             break
      return history
 </code-python>
@@ Строка 89: / Строка 112: @@
 Он принимает на вход описание машины Тьюринга в виде хэш-таблицы — рассмотрим пример машины тьюринга для задачи удвоения входной строки (алфавит состоит только из «1»).
-Табличное описание МТ:
+Описание соответствующей МТ:
-−
-<latex>
-\begin{tabular}{|cc|c|ccc|}
-\hline
- <\textcolor{blue}{s1}> & * & $\Rightarrow$ & [\textcolor{red}{q}] & * &  \\ \hline
- <\textcolor{blue}{s1}> & 1 & $\Rightarrow$ & s2 & * & R \\ \hline
- s2 & * & $\Rightarrow$ & s3 & * & R \\ \hline
- s2 & 1 & $\Rightarrow$ & s2 & 1 & R \\ \hline
- s3 & * & $\Rightarrow$ & s4 & 1 & L \\ \hline
- s3 & 1 & $\Rightarrow$ & s3 & 1 & R \\ \hline
- s4 & * & $\Rightarrow$ & s5 & * & L \\ \hline
- s4 & 1 & $\Rightarrow$ & s4 & 1 & L \\ \hline
- s5 & * & $\Rightarrow$ & <\textcolor{blue}{s1}> & 1 & R \\ \hline
- s5 & 1 & $\Rightarrow$ & s5 & 1 & L \\ \hline
-\end{tabular}
-</latex>
-−
-Таблица МТ в виде [[Python]]-структуры для вышеприведенного симулятора:
 <code-python>
 MT={

← Предыдущая	Версия 16:48, 23 октября 2008
(нет различий)