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

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

теоремам 4.2 и 4.3 если эта проблема разрешима хотя бы в одной системе, то она разрешима и в другой.

Выводы :

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

В силу тезиса Тьюринга, любой алгоритм реализуем  в  терминах действий последовательной, параллельной композиций, выбора  и цикла и базового набора действий;

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

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

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

Вопросы :

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

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

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

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

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

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

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

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

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

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

 Если Fa (*P), то M(1||Q*aR)o U*o U1  иначе U0o U*o Ui+1?

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: