Категория
Информатика
Тип
реферат
Страницы
4 стр.
Дата
27.10.2008
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
18534.zip — 21.09 kb
  • sushhestvovanie-universalnyx-vychislitelej-algoritmicheskie-problemy-i-vzaimosvjaz-algorit_18534_1.rtf — 224.33 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Существование универсальных вычислителей
Существование универсальных вычислителей.
Алгоритмические проблемы и взаимосвязь алгоритмических систем.
Существование универсальных вычислителей.
Теперь задумаемся вот о чём. Каждый раз, когда мы строили программу для новой Машины Тьюринга, даже если мы при этом использовали программы для других машин, не явно предполагалось, что как-то, где-то, кем-то строилась каретка, обладающая заданным набором состояний, способная распознавать и записывать символы из заданного алфавита и т
.п. Построение такой каретки - сама по себе задача не из простых
. Для каждого нового алгоритма мы вынуждены строить новый исполнитель.
Это выглядит примерно так, как если бы для каждой новой программы нам надо было строить новый компьютер.
А нельзя ли построить такой исполнитель, который был бы способен выполнить любой алгоритм, заданный в виде программы для Машины Тьюринга
? Положительный ответ на этот вопрос являлся бы математическим обоснованием существования универсального вычислителя, т.е. способного выполнить любой должным образом записанный алгоритм, вычислить любую вычислимую функцию.
Итак, пусть нам надо построить Универсальную Машину Тьюринга, назовём её
УМТ, для которой:
исходными данными являются программа другой машины, назовём её МТ, с исходными данными Д последней;
результат применения УМТ к этим исходным данным должен быть таким же, как применение МТ к её исходным данным, то есть
УМТ(МТ,Д)=МТ(Д).
Из-за чисто технической громоздкости мы не будем давать полного доказательства существования УМТ, а дадим лишь обоснование её существования. В этом обосновании мы покажем основную идею доказательства.
Представим себя в качестве такой



Ваше мнение



CAPTCHA