Является ли число омега математическим оракулом?

Доступ к эксклюзивному контенту на Patreon: https://www.patreon.com/user?u=86649007

#alanturing #turingmachines #logic #complexity #omega #computerscience #happybirthday

В информатике мы изучаем поведение программ. Один из центральных вопросов — проблема остановки, сформулированная известным математиком Аланом Тьюрингом. Останавливается ли любая программа или нет? Мы исследуем, насколько далеко мы можем продвинуться в этом вопросе, используя число Омега, определенное Грегори Хайтином. Мы также обсуждаем колмогоровскую сложность, азартные игры, сопоставление с образцом и многое другое.

Если вы хотите узнать больше, воспользуйтесь следующими ссылками:

[WIKI 1] https://en.wikipedia.org/wiki/Kolmogo...

[WIKI 2] https://en.wikipedia.org/wiki/Halting...

[SCIAM 1] «Математические игры», Мартин Гарднер, Scientific American, ноябрь 1979 г., стр. 22

Содержание:
0:00 Введение
1:34 Случайное = несжимаемое
4:14 Большинство действительных чисел случайны
7:10 Случайное = непредсказуемое
9:40 Алан Тьюринг и проблема остановки
13:19 Число омега
15:46 Как работает оракул
19:57 Оракул навсегда вне досягаемости

Это видео опубликовано по лицензии CC Attribution
( https://creativecommons.org/licenses/... )