Реферат: Существование универсальных вычислителей. Алгоритмические проблемы и взаимосвязь алгоритмических систем.

Проблема самоприменимости алгоритмической системы алгоритмически не разрешима;

Если алгоритмическая проблема не разрешима, то она не разрешима в любой другой эквивалентной алгоритмической системы;

Алгоритмические системы МТ и НАМ эквивалентны.

Вопросы :

Что такое интерпретация?

Что такое кодирование?

В чем проблема линеаризации Ф.с. для МТ?

Что такое универсальный исполнитель:
- он может исполнять заданный А в любой А.с.?
- он может исполнять любой А, выразимый в данной А.с.?

Как решается проблема произвольности алфавита в УМТ?

Что такое А.п.?

Самоприменимость - что это такое?

А.п. самоприменимости разрешима?

В МТ А не закончен если нет применимого правила, в НАМ в этом случае А - закончен. Как это несоответствие решается при доказательстве сводимости МТ к НАМ и наоборот?

Что означает запись:

Если F_a (*P), то M(1||Q*aR)o U^* o U₁ иначе U₀ o U^* o U_i+1 ?