Документ взят из кэша поисковой машины. Адрес оригинального документа : 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 г.