5
правок
Изменения
Новая страница: «{{Определение |definition = Детерминированная машина Тьюринга <tex>\langle Q,\sum,\Gamma,b_0,\Delta,\{q_s\},\{q_a\}\rangle<…»
{{Определение
|definition =
Детерминированная машина Тьюринга <tex>\langle Q,\sum,\Gamma,b_0,\Delta,\{q_s\},\{q_a\}\rangle</tex> допускает слово <tex>w\in \Sigma^{*}</tex>, если для некоторых <tex>m\in \mathbb{N}</tex> и <tex>n\in \mathbb{N}</tex> <tex>\langle \epsilon,q_s,b_0,w\rangle \vdash^{*}\langle b_0^{m},q_a,b_0,b_0^{n}\rangle</tex>
}}
{{Определение
|definition =
Язык, допускаемый машиной Тьюринга <tex>M</tex>, - это язык, состоящий из всех допускаемых данной машиной Тьюринга слов.
}}
{{Определение
|definition =
Язык называется <b>перечеслимым (рекурсивно перечислимым, полуразрешимым)</b>, если существует детерминированная машина Тьюринга, допускающая этот язык.
}}
{{Теорема
|id=th1
|statement=
Любой разрешимый язык является перечислимым.
|proof=
Пусть дана машина Тьюринга <tex>M=\langle Q,\sum,\Gamma,b_0,\Delta,\{q_s\},\{q_a, q_r\}\rangle</tex>, которая разрешает язык <tex>L</tex> тогда машина Тьюринга <tex>M'=\langle Q,\sum,\Gamma,b_0,\Delta,\{q_s\},\{q_a\}\rangle</tex> допускает язык <tex>L</tex>
}}
|definition =
Детерминированная машина Тьюринга <tex>\langle Q,\sum,\Gamma,b_0,\Delta,\{q_s\},\{q_a\}\rangle</tex> допускает слово <tex>w\in \Sigma^{*}</tex>, если для некоторых <tex>m\in \mathbb{N}</tex> и <tex>n\in \mathbb{N}</tex> <tex>\langle \epsilon,q_s,b_0,w\rangle \vdash^{*}\langle b_0^{m},q_a,b_0,b_0^{n}\rangle</tex>
}}
{{Определение
|definition =
Язык, допускаемый машиной Тьюринга <tex>M</tex>, - это язык, состоящий из всех допускаемых данной машиной Тьюринга слов.
}}
{{Определение
|definition =
Язык называется <b>перечеслимым (рекурсивно перечислимым, полуразрешимым)</b>, если существует детерминированная машина Тьюринга, допускающая этот язык.
}}
{{Теорема
|id=th1
|statement=
Любой разрешимый язык является перечислимым.
|proof=
Пусть дана машина Тьюринга <tex>M=\langle Q,\sum,\Gamma,b_0,\Delta,\{q_s\},\{q_a, q_r\}\rangle</tex>, которая разрешает язык <tex>L</tex> тогда машина Тьюринга <tex>M'=\langle Q,\sum,\Gamma,b_0,\Delta,\{q_s\},\{q_a\}\rangle</tex> допускает язык <tex>L</tex>
}}
