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