Дмитрий Радищев (dibr) wrote,
Дмитрий Радищев
dibr

О границах познаваемого

Оригинал взят у vadim_proskurin в О границах познаваемого


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

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

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

Предвижу нашествие гуманитариев в комментах

Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments