Основы теории вычислимых функций

Двухстороннее исчисление, для правил которого нет алгоритма, выясняющегося, можно ли получить одно слово из другого:

(Отметьте один правильный вариант ответа.)

Варианты ответа

не существует

неопределенно

существует(Верный ответ)

Похожие вопросы

Ассоциативное исчисление - это:

Ассоциативное исчисление - двустороннее, если оно содержит правила:

Утверждение "Всякое исчисление, порождающее формулы арифметики либо не адекватно, либо неполно" - это:

Перечислимое множество, для которого прямой пересчет его дополнения неограничен сверху вычислимой функцией является:

По программам функций f и g получить их композицию:

В алфавите X слово P выводимо из слова Q, если:

По любой вычислимой функции можно указать:

Для любых $х_0, х_1, \ldots , х_n \in N$ можно найти такие числа a и b, что: