June 13th, 2021

404

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

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

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