Разрешимые языки типа 0

[Tookser]

Я читал, что существуют разрешимые языки, принадлежащие к типу 0 по иерархии Хомского, но никак не могу придумать примеров этому. Помогите, пожалуйста, придумать такой язык.

[mihaild]

Ну например что вы можете сказать про разрешимость и перечислимость языков типов 0 и 1?

[Tookser]

mihaild, языки типов 0 и 1 перечислимы, языки типа 1 разрешимы. Ещё я читал, но не знаю, как доказать, что существуют разрешимые языки типа 0.

[mihaild]

Tookser, вы умеете доказывать, что все перечислимые языки можно описать грамматикой типа 0?
(если да - то вопрос сводится к построению перечеслимого неразрешимого множества; если нет - то наверное проще сначала доказать это)

[Tookser]

mihaild, да, умею.
Я знаю, что существует перечислимое неразрешимое множество, и могу его построить. Меня интересует перечислимое разрешимое множество типа 0.
P.S. Под языком типа 0 я имел в виду язык, который описывается грамматикой типа 0, но не описывается грамматикой типа 1.

[mihaild]

Tookser, а, простите, я читать не умею.

Тогда посмотрим на алгоритм, распознающий языки типа 1 - ему достаточно полиномиальной памяти. Из теоремы об иерархии по памяти следует, что $PSPACE \neq EXPSPACE$. Соответственно, достаточно взять любой $EXPSPACE$-трудный разрешимый язык (например, множество пар (МТ, $n$) таких, что МТ останавливается, использовав не более $2^n$ памяти).

[Tookser]

К сожалению, я не всё сейчас понимаю. Разберусь попозже, наверное.

Скажите хотя бы, как выглядит алгоритм, распознающий языки типа 1, требующий полиномиальной памяти?