Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://al.cs.msu.su/static/seminars/catfl/reports/025_troubles/abstract.html
Дата изменения: Mon Nov 19 20:21:18 2007 Дата индексирования: Mon Oct 1 20:09:24 2012 Кодировка: koi8-r |
Мерзляков В.В., 24 октября 2007
В данном докладе рассматриваются вопросы существования сколь угодно сложных
задач. Для этого используется аппарат машин Тьюринга. Выделены три части
доклада.
1)В первой части даётся общий обзор машин Тьюринга, устанавливаются
соглашения об обозначениях.
2)Во второй части описывается некое семейство
машин Тьюринга, которое примечательно тем, что все машины, входящие в это
семейство, можно занумеровать. Так же вводятся понятия вычислимых и
общерекурсивных функций.
3)В третьей части доказываются две основные теоремы
о существовании сколь угодно сложных задач. При доказательстве теорем активно
используются факты из второй части доклада.
Основная литература - книга В.Б.Алексеева "Введение в теорию сложности алгоритмов" издательство факультета ВМиК МГУ 2002 г.