?

Log in

No account? Create an account
vadim_proskurin's Journal -- Day [entries|friends|calendar]
vadim_proskurin

Locations of visitors to this page
[ userinfo | livejournal userinfo ]
[ calendar | livejournal calendar ]

О границах познаваемого [22 Sep 2017|09:21pm]


В позапрошлом веке философы много спорили, познаваем ли мир, и если да, то до какой степени. Сейчас любому образованному человеку известно, что мир непознаваем, существуют достоверно неразрешимые задачи, например, задача остановки произвольной машины Тьюринга. Соответствующая теорема имеет простое следствие: существует конкретная машина Тьюринга (например, универсальная машина Тьюринга), для которой эта задача неразрешима. Другими словами, существует конкретный математический объект, для которого строго доказано, что некоторые его свойства непознаваемы.

До последнего времени математики ограничивались доказательством того, что подобные объекты существуют, предъявлять конкретные примеры никто не пытался. Казалось интуитивно понятным, что подобные объекты должны быть неимоверно сложными.

В прошлом году некий Adam Yedidia (на фото), аспирант из MIT, построил конкретную машину Тьюринга из 7918 состояний, для которой доказал, что задача ее остановки неразрешима в рамках общепринятой теории множеств. Другими словами, предъявлен конкретный непознаваемый объект, и он оказался вовсе не астрономически сложным, его заархивированное описание занимает всего 8.5М.

Предвижу нашествие гуманитариев в комментах
30 comments|post comment

navigation
[ viewing | September 22nd, 2017 ]
[ go | previous day|next day ]