Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Из Википедии — свободной энциклопедии

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

Теория вычислимости берёт своё начало от работы Алана Тьюринга (1936) «On Computable Numbers, With An Application to Entscheidungsproblem», в которой он ввел понятие абстрактной вычислительной машины, получившей впоследствии его имя, и доказал фундаментальную теорему о неразрешимости задачи о её остановке. Знаменитая теорема Гёделя о неполноте (1931) была доказана в терминах примитивно рекурсивных функций, класс которых в 1934 году Гёдель расширил до класса общерекурсивных функций. Формализм, развитый Гёделем, оказался эквивалентным тьюринговскому (а также многим другим). Вместе с тезисом Чёрча — Тьюринга этот факт явно продемонстрировал содержательность новой теории, и сейчас эти определения общеприняты в качестве формального аналога алгоритмически вычислимых функций.

«Определение вычислимых функций, данное Гёделем, носило синтаксический характер, и лишь установление совпадения этого класса с классом общерекурсивных функций (вместе с формулировкой и «принятием» тезиса Чёрча) показало действительную значимость теоремы о неполноте.
Ершов, Юрий Леонидович
»

Энциклопедичный YouTube

  • 1/5
    Просмотров:
    26 460
    1 571
    12 418
    842
    10 480
  • Введение в логику, урок 4: Предикаты и кванторы
  • Основы вычислимости и теории сложности, лекция 1
  • Введение в логику, урок 5: Теории: интуиции
  • А.Б. Сосинский. (Не)вычислимость [А. Тюринг]
  • Математическая логика и теория алгоритмов | Трейлер к курсу

Субтитры

См. также

Математики, заложившие основы теории вычислимости


Литература

  • Булос Дж., Джеффри Р. Вычислимость и логика. — М.: Мир, 1994. — 396 с.
  • Ершов Ю.Л. Теория нумераций. — М.: Наука, 1977. — 416 с.
  • Катленд Н. Вычислимость. Введение в теорию рекурсивных функций.. — М.: Мир, 1986. — 256 с.
  • Клини. Введение в метаматематику. — М.: Издательство иностранной литературы, 1957. — 526 с.
  • Мальцев А.И. Алгоритмы и рекурсивные функции. — М.: Наука, 1965. — 392 с.
  • Манин Ю.И. Вычислимое и невычислимое. — М.: Советское радио, 1980. — 128 с.
  • Минский М. Вычисления и автоматы. — М.: Мир, 1971. — 366 с.
  • Ходжерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.: Мир, 1972. — 624 с.
  • Барвайс Дж. Справочная книга по математической логике в четырёх частях. Часть III. Теория рекурсии.. — М.: Наука, 1982. — 360 с.
  • Успенский В.А. Лекции о вычислимых функциях. — М.: Физматгиз, 1960. — 492 с.
  • Успенский В.А., Семёнов Л.А. Теория алгоритмов: основные открытия и приложения. — М.: Наука, 1987.
  • Шенфилд Дж. Степени неразрешимости. — М.: Наука, 1977. — 192 с.

Ссылки

Эта страница в последний раз была отредактирована 22 июля 2020 в 19:57.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).