Теория вычислимости

Теория вычислимости, также известная как теория рекурсивных функций, — это раздел современной математики, лежащий на стыке математической логики, теории алгоритмов и информатики. Что такое алгоритм? и Что такое эффективный алгоритм? Что такое доказательство? Как доказать, что нет алгоритма, который решит данную задачу? Как доказать, что что-то нельзя доказать? Как понять, что нет эффективного алгоритма для данной задачи? Что такое вычислимые функции, арифметическая иерархия, колмогоровская сложность? Что же на самом деле могут вычислительные системы? и Где границы их возможностей? На эти и многие другие вопросы попытается ответить Григорий Николаевич Жолткевич — д.т.н, заведующий кафедрой теоретической и прикладной информатики Харьковского национального университета им. В.Н. Каразина.