Формальное понятие вычислимости

Ещё один эпизод, где Джунферно напрямую монетизирует своё бакалаврское образование.

Patreon:   / junferno  
Twitter:   / junferno  
Tumblr: https://www.tumblr.com/junferno
Twitch:   / junferno  
Discord:   / discord     / discord  

Сноски:
Основателем проблемы «Entscheidungsproblem» был Лейбниц, который задумался над ней после разработки механической вычислительной машины в XVII веке. Гильберт сформулировал эту проблему совместно с Вильгельмом Аккерманом в продолжение своей программы проблем, которые он считал важнейшими математическими проблемами XX века (включая гипотезу Римана).
– Общерекурсивные функции (или мю-рекурсивные функции) впоследствии легли в основу теории рекурсии, основанной Рожей Петером на трудах Гёделя.
– Лямбда-исчисление Чёрча впоследствии повлияло на нотацию функционального языка программирования Lisp, хотя изначально Lisp не был производным от лямбда-исчисления.
– Тьюринг-полный означает «способный моделировать любую машину Тьюринга». Тьюринг-полные машины существовали и до Тьюринга, но их потенциал не был реализован в полной мере, например, аналитическая машина Чарльза Бэббиджа 1837 года, разработанная для арифметических вычислений. Ада Лавлейс была первой, кто осознал, что машина Бэббиджа может быть использована для более сложных логических операций. Её заметка (1842–1843) об использовании машины для вычисления последовательности чисел Бернулли часто упоминается как первая компьютерная программа. - В своей оригинальной статье Тьюринг называл свои машины не «машинами Тьюринга», а логическими вычислительными машинами (ЛВМ). Вместо доказательства логических утверждений они «вычисляли числа», то есть генерировали числа поразрядно. Числа, которые могли быть получены с помощью НВМ, были «вычислимыми числами». Отрицательное доказательство Тьюрингом проблемы «вывода» касалось не проблемы остановки, а вычисления того, выведет ли машина когда-либо цифру 0. Однако это было эквивалентно вычислительным задачам, поскольку логические утверждения можно кодировать числами (см. нумерацию Гёделя).
Подход Поста к вычислимости во многом основывался на человеческом разуме, в отличие от рационального подхода Гёделя. Всего через несколько месяцев после публикации статьи Тьюринга Пост разработал модель, эквивалентную машинам Тьюринга, независимую от Тьюринга, в которой использовалось двустороннее бесконечное «символическое пространство». Таким образом, в видео утверждается, что Пост одновременно «согласен и не согласен» с машиной Тьюринга, поскольку (насколько я могу судить) независимый подход Поста эквивалентен математически, но не столь уж философски.
Распространённое заблуждение заключается в том, что Тьюринг утверждал, что ни одна машина не может вычислить то, что не может машина Тьюринга. Тьюринг никогда не заявлял об этом прямо, а лишь предложил определение «эффективной вычислимости», но эта тема до сих пор остаётся предметом дискуссий. Хотя существуют теории квантовых «гипервычислений», квантовые вычисления в том виде, в каком мы их знаем (Deutsch 1985, представлено в 13:34), обладают той же вычислительной мощностью, что и машины Тьюринга, только быстрее. Однако Дойч утверждает, что его принцип Чёрча-Тьюринга-Дойча охватывает все физические процессы.
Тезис Чёрча-Тьюринга продолжает оставаться общепринятым, поскольку все разработанные альтернативные модели вычислимости (Пост, Шёнфинкель, Карри, Марков) в конечном итоге оказываются эквивалентными вычислимости по Тьюрингу. - Тьюринг провел последние годы жизни, разрабатывая концепцию компьютера с хранимой в памяти программой вместе с Джоном фон Нейманом, создавшим архитектуру фон Неймана.
Речь Давида Гильберта «Математика не знает рас и географических границ; для математики культурный мир — это единая страна» была произнесена в связи с отчуждением немецких математиков после Первой мировой войны. Вероятно, он не смог произнести ее из-за плохого здоровья. Тем не менее, Гильберт продолжал поддерживать еврейских студентов и коллег. В 1934 году Гильберт, обращаясь к нацистскому министру образования по поводу отстранения евреев от академической сферы, сказал: «В Геттингене больше нет математики».
В 1939 году Курт Гёдель бежал из оккупированной нацистами Австрии в Принстонский университет, где подружился с немецким физиком-евреем Альбертом Эйнштейном. - В 1952 году, несмотря на дерзкие сообщения, имевшие решающее значение для победы Великобритании над фашизмом, Алан Тьюринг был привлечен к ответственности за «гомосексуальные действия» британским правительством. Он скончался в 1954 году.

Ссылки: https://www.junferno.com/references/#....

Фотографии предоставлены Wikimedia Commons, Sega
3D-модели через Sketchfab, любезно предоставлены Camronac.
Лицензионная музыка Лицензия Creative Commons Attribution (разрешено повторное использование) J-POP Karaoke - きただにひろし - ウィーアー!(アニメ『ONE PIECE』OP)
Кадры игрового процесса предоставлены Сибли, мэром Мори и Тайгером.
Junferno ...