Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Теорія обчислюваності



Теорія обчислюваності - це розділ сучасної математики і теорії обчислень, що виник в результаті вивчення понять вичіслімості і невичіслімості. Спочатку теорія була присвячена вичіслімих і невичіслімим функцій і порівнянню різних моделей обчислень. Зараз поле дослідження теорії обчислюваності розширилося - з'являються нові визначення поняття вичіслімості і йде злиття з математичною логікою, де замість вичіслімості і невичіслімості йдеться про доказовою і недовідності (виводимості і невиводимість) тверджень в рамках будь-яких теорій.

Теорія обчислюваності бере свій початок від дисертації Тьюринга ( 1936), в якій він ввів поняття абстрактної обчислювальної машини, що отримала згодом його ім'я, і довів фундаментальну теорему про нерозв'язності задачі про її зупинці. Знаменита теорема Геделя про неповноту ( 1931) була доведена в термінах примітивно рекурсивних функцій, клас яких у 1934 році Гедель розширив до класу общерекурсівних функцій. Формалізм, розвинений Геделем виявився еквівалентним тьюрінговскому (а також багатьом іншим). Разом з Тезою Черча - Тьюринга цей факт явно продемонстрував змістовність нової теорії, і зараз ці визначення загальноприйняті в якості формального аналога алгоритмічно вичіслімих функцій.

Визначення вичіслімих функцій, дане Геделем, носило синтаксичний характер, і лише встановлення збігу цього класу з класом общерекурсівних функцій (разом з формулюванням і "прийняттям" тези Черча) показало дійсну значимість теореми про неповноту. Єршов, Юрій Леонідович

В даний час дослідження з теорії обчислюваності активно ведуться в усіх країнах світу. Росія завжди була одним зі світових центрів досліджень з теорії обчислюваності і її додатків. Ці дослідження беруть початок від ранніх робіт Маркова і Мальцева з теорії алгоритмів і її зв'язкам з алгеброю, ознаменувалися вирішенням проблеми Посту Мучник. Ці дослідження сьогодні тривають на дуже високому рівні в багатьох наукових центрах Росії (школа Єршова в Новосибірську, школа Арсланова в Казані) та інших країн колишнього Радянського Союзу (Алма-Ата, Казахстан).

Слід виділити: Теорему Райс, проблем зупинити
Математики, що заклали основи теорії обчислюваності:


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Теорія
М-теорія
Теорія
Теорія 4P
Теорія перспектив
Теорія Реджо
Теорія всього
Теорія геосинкліналей
Теорія перколяції
© Усі права захищені
написати до нас
Рейтинг@Mail.ru