Математики — НЕ грёбаные читеры

Я писал комментарий к посту Алексея Ивановича «Математики — грёбаные читеры» про новое видео Тома Скотта про то, как математики доказали, что есть задачи, которые компьютеры не могут решить, но комментарий получился большим, так что я решил вынести его в отдельный пост. И заодно посоветовать всем подписываться на Алексея Ивановича.

Во-первых, подпишитесь на Алексея Ивановича. В своем блоге он пишет про разработку игр и про технологии, т.е. о том же, о чем и я, но по какой-то причине у него мало подписчиков.

Теперь по теме. В своем посте «Математики — грёбаные читеры» он высказал интересное мнение. Он пишет, что математики взяли не самый полезный на практике пример с задачей определения бесконечных циклов, свели его к парадоксу, и никому таким образом особо не помогли. Я мог случайно переврать его мнение, поэтому лучше прочитайте оригинал здесь:

Я с ним не совсем согласен, поэтому решил написать о задаче вычислимости в частности и математике в целом.

Под самим видео есть закрепленный комментарий от авторов:

Т.е. они сами переживают, что упростили настолько, что могли что-то испортить. Но суть они как раз сохранили. В видео Том кратко рассказывает о теории вычислимости в информатике и о том, как Алан Тьюринг предложил свое определение вычислимости, которое сейчас называют «Машина Тьюринга». С помощью этого определения можно найти задачи, которые не являются вычислимыми, т.е. доказать, что есть задачи, которые компьютер не в состоянии решить.

Это в каком-то смысле аналог размышления «Если бог может все, то может ли он создать камень, который не сможет поднять»? Получается, здесь философы нашли контр-пример, который доказывает то, что бог не всемогущ, сводя выражение к противоречию (парадоксу). Сведение к противоречию — это вообще один из основных методов доказательства/опровержения в математической логике.

Теперь переходим к задаче вычислимости (solvability или computability). Здесь все то же самое. Математики нашли контр-пример, который доказывает, что компьютеры не могут вычислить все. С точки зрения математики, этого достаточно. Возможно, это не единственная задача, которую компьютеры не могут решить, но так устроена математика — тебе достаточно найти всего один контр-пример, чтобы опровергнуть гипотезу.

Да, тут все опирается на определение вычислимости через машину Тьюринга. Есть еще вычислимость через частично рекурсивные функции Гёделя, через машину Поста и другие. У меня в списке идей для блога есть тема про полноту по Тьюрингу, но в прикладном смысле, а не в математическом. Когда-нибудь дойдут руки и напишу.

Не разрешится. Если такая программа возможна, то мы уже нашли противоречие. Если программа Halts не возможна, то это сразу автоматические доказывает, что есть задачи, которые нельзя решить — Halts одна из них. Это математика, тут все строго:)

Это же математика, абстракция — это ее сила. Есть такой раздел математики — топология. С точки зрения топологии, кружка и бублик — это одна и та же форма. А человек идентичен предмету с 4 дырками: рот, две ноздри, анус, а остальное — это просто поверхность с неровностями, которыми можно пренебречь. Люди сейчас в космос летают и используют спутниковую навигацию, потому что кто-то несколько сотен лет назад занимался задачами, абстрагированными от реальности. Кто знает, как сегодняшние открытия, помогут ученым через 50-100-200 лет?

В общем, смысл моего поста не в том, чтобы как-то доказать, что кто-то в интернете не прав, а чтобы высказать мое мнение, что математика — это круто. Ну и подписывайтесь на Алексея Ивановича, да.