amarao (amarao_san) wrote,
amarao
amarao_san

Category:

О конечном автомате, который себя вообразил компьютером

Внезапно, я сейчас осознал интересный plot twist для self-reference systems. Допустим, у нас есть тьюринг-машина (обычный компьютер, для удобства обсуждения, без дисков и сети, только память). Допустим, этот компьютер задумался "о себе", и решил пересчитать все возможные свои состояния. Его память N бит, т.е. у него может быть не более чем 2^N состояний. Так вот, для хранения числа 2^N, нам надо N бит, и ничего, кроме числа возможных состояний компьютер хранить в себе не сможет.

Другими словами, self-referencing система не может проанализировать все свои действия. Более того, если код занимает ненулевое число бит, то даже пересчитать не может.
Subscribe

  • Проблемы от ipv6

    Всех интересует, какие проблемы от него. И вот я накопал. Ничего существенного, но то, что есть, раздражает и усложняет. 1. В половине софта…

  • Дурацкий срачик с сетевиками

    Должен ли VRRPv3 для ipv6 слать RA для собственных link-local адресов? (которые не virtual)? Мне кажется, что нет, потому что если он ляжет, то…

  • первая загадка ipv6

    Дано: планшет с ip 2a00:11d8:1201:32b0:b071:aca2:48f5:fecf 1) Проходит тест на test-ipv6.com 10/10 2) Отвечает на пинги с машины в одной с ним сети…

  • 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.
  • 3 comments