https://camokathomelab.servebeer.com/mediawiki/index.php?action=history&feed=atom&title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8 2026-07-19T09:15:22Z История изменений этой страницы в вики MediaWiki 1.45.3 https://camokathomelab.servebeer.com/mediawiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8&diff=39015&oldid=prev 2025-08-31T13:46:16Z

<p>Замена параметров <a href="/mediawiki/index.php?title=%D0%A8:rq&amp;action=edit&amp;redlink=1" class="new" title="Ш:rq (страница не существует)">ш:rq</a> на вложенные шаблоны с датами установки: wikify → <a href="/mediawiki/index.php?title=%D0%A8:%D0%BF%D0%BB%D0%BE%D1%85%D0%BE%D0%B5_%D0%BE%D1%84%D0%BE%D1%80%D0%BC%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5&amp;action=edit&amp;redlink=1" class="new" title="Ш:плохое оформление (страница не существует)">ш:плохое оформление</a> (<a href="/mediawiki/index.php/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%98%D0%B7%D0%BC%D0%B5%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F/60330082" title="Служебная:Изменения/60330082">2013-12-26</a>), sources → <a href="/mediawiki/index.php?title=%D0%A8:%D0%BD%D0%B5%D1%82_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%BE%D0%B2&amp;action=edit&amp;redlink=1" class="new" title="Ш:нет источников (страница не существует)">ш:нет источников</a> (<a href="/mediawiki/index.php/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%98%D0%B7%D0%BC%D0%B5%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F/60330082" title="Служебная:Изменения/60330082">2013-12-26</a>)</p> <p><b>Новая страница</b></p><div>__NOTOC__<br /> &#039;&#039;&#039;Теория вычислимости&#039;&#039;&#039; — раздел [[математика|математики]], лежащий на стыке [[Математическая логика|математической логики]], [[Теория вычислений|теории алгоритмов]] и [[Информатика|информатики]], возникшей в результате изучения понятий вычислимости и невычислимости. Изначально теория была посвящена [[Вычислимые функции|вычислимым]] и невычислимым функциям и сравнению различных [[Модель вычислений|моделей вычислений]]. В наши дни поле исследования теории вычислимости расширилось — появляются новые определения понятия вычислимости и идёт слияние с [[Логика|математической логикой]], где вместо вычислимости и невычислимости идёт речь о доказуемости и недоказуемости (выводимости и невыводимости) утверждений в рамках каких-либо теорий.<br /> <br /> Теория вычислимости берёт своё начало от работы [[Тьюринг, Алан|Алана Тьюринга]] (1936) «On Computable Numbers, With An Application to Entscheidungsproblem», в которой он ввёл понятие абстрактной вычислительной машины, получившей впоследствии его имя, и доказал фундаментальную теорему о [[проблема остановки|неразрешимости задачи о её остановке]]. Независимо в то же время схожий формализм ввёл [[Пост, Эмиль Леон|Эмиль Пост]] ([[машина Поста]]). [[Теорема Гёделя о неполноте]] (1931) была доказана в терминах [[Примитивно рекурсивная функция|примитивно рекурсивных функций]], класс которых в 1934 году [[Гёдель, Курт|Гёдель]] расширил до класса [[Общерекурсивная функция|общерекурсивных функций]]. Формализм, развитый Гёделем, оказался эквивалентным тьюринговскому (а также многим другим). Вместе с [[Тезис Чёрча — Тьюринга|тезисом Чёрча — Тьюринга]] этот факт явно продемонстрировал содержательность новой теории, и сейчас эти определения общеприняты в качестве формального аналога алгоритмически вычислимых функций.<br /> <br /> {{цитата|автор=[[Ершов, Юрий Леонидович]]|Определение вычислимых функций, данное Гёделем, носило синтаксический характер, и лишь установление совпадения этого класса с классом общерекурсивных функций (вместе с формулировкой и «принятием» тезиса Чёрча) показало действительную значимость теоремы о неполноте.}}<br /> <br /> == Литература ==<br /> * {{книга <br /> |автор=Булос Дж., Джеффри Р.<br /> |заглавие= Вычислимость и логика<br /> |место=М.<br /> |издательство= Мир<br /> |год= 1994<br /> |страниц= 396 }}<br /> * {{книга <br /> |автор=Ершов Ю.Л.<br /> |заглавие= Теория нумераций<br /> |место=М.<br /> |издательство= Наука<br /> |год= 1977<br /> |страниц= 416}}<br /> * {{книга <br /> |автор=Катленд Н.<br /> |заглавие= Вычислимость. Введение в теорию рекурсивных функций.<br /> |место=М.<br /> |издательство= Мир<br /> |год= 1986<br /> |страниц= 256}}<br /> * {{книга <br /> |автор=Клини<br /> |заглавие= Введение в метаматематику<br /> |место=М.<br /> |издательство= Издательство иностранной литературы<br /> |год= 1957<br /> |страниц= 526}}<br /> * {{книга <br /> |автор=Мальцев А.И.<br /> |заглавие= Алгоритмы и рекурсивные функции<br /> |место=М.<br /> |издательство= Наука<br /> |год= 1965<br /> |страниц= 392}}<br /> * {{книга <br /> |автор=Манин Ю.И.<br /> |заглавие= Вычислимое и невычислимое<br /> |место=М.<br /> |издательство= Советское радио<br /> |год= 1980<br /> |страниц= 128}}<br /> * {{книга <br /> |автор=Минский М.<br /> |заглавие= Вычисления и автоматы<br /> |место=М.<br /> |издательство= Мир<br /> |год= 1971<br /> |страниц= 366}}<br /> * {{книга <br /> |автор=Ходжерс Х.<br /> |заглавие= Теория рекурсивных функций и эффективная вычислимость<br /> |место=М.<br /> |издательство= Мир<br /> |год= 1972<br /> |страниц= 624}}<br /> * {{книга <br /> |автор=Барвайс Дж.<br /> |заглавие= Справочная книга по математической логике в четырёх частях. Часть III. Теория рекурсии.<br /> |место=М.<br /> |издательство= Наука<br /> |год= 1982<br /> |страниц= 360}}<br /> * {{книга <br /> |автор=Успенский В.А.<br /> |заглавие= Лекции о вычислимых функциях<br /> |место=М.<br /> |издательство= Физматгиз<br /> |год= 1960<br /> |страниц= 492}}<br /> * {{книга <br /> |автор=Успенский В.А., Семёнов Л.А.<br /> |заглавие= Теория алгоритмов: основные открытия и приложения<br /> |место=М.<br /> |издательство= Наука<br /> |год= 1987<br /> |страниц= }}<br /> * {{книга <br /> |автор=Шенфилд Дж.<br /> |заглавие= Степени неразрешимости<br /> |место=М.<br /> |издательство= Наука<br /> |год= 1977<br /> |страниц= 192}}<br /> {{rq|<br /> {{плохое оформление|дата=2013-12-26}}<br /> {{нет источников|дата=2013-12-26}}<br /> }}<br /> {{Перевести|en|Computability theory}}<br /> {{Логика}}<br /> {{Основные направления информатики}}<br /> <br /> [[Категория:Теория алгоритмов]]<br /> [[Категория:Математическая логика]]</div>

imported>Sldst-bot