Перечислимые языки

Определение:

Детерминированная машина Тьюринга [math]\langle Q,\sum,\Gamma,b_0,\Delta,\{q_s\},\{q_a\}\rangle[/math] допускает слово [math]w\in \Sigma^{*}[/math], если для некоторых [math]m\in \mathbb{N}[/math] и [math]n\in \mathbb{N}[/math] [math]\langle \epsilon,q_s,b_0,w\rangle \vdash^{*}\langle b_0^{m},q_a,b_0,b_0^{n}\rangle[/math]

Определение:

Язык, допускаемый машиной Тьюринга [math]M[/math], - это язык, состоящий из всех допускаемых данной машиной Тьюринга слов.

Определение:

Язык называется перечеслимым (рекурсивно перечислимым, полуразрешимым), если существует детерминированная машина Тьюринга, допускающая этот язык.

Теорема:

Любой разрешимый язык является перечислимым.

Доказательство:

[math]\triangleright[/math]

Пусть дана машина Тьюринга [math]M=\langle Q,\sum,\Gamma,b_0,\Delta,\{q_s\},\{q_a, q_r\}\rangle[/math], которая разрешает язык [math]L[/math] тогда машина Тьюринга [math]M'=\langle Q,\sum,\Gamma,b_0,\Delta,\{q_s\},\{q_a\}\rangle[/math] допускает язык [math]L[/math]

[math]\triangleleft[/math]