Трансляция виртуальных адресов как тьюринг-полный язык

Вот очень странный и невероятно крутой хак: trapcc - вычисление без единой инструкции CPU.

Авторы продемонстрировали, что механизм трансляции адресов на архитектуре x86 обладает полнотой Тьюринга, т.е. с его помощью можно реализовать любой алгоритм. С помощью хитрой настройки различных контрольных таблиц, которыми пользуется процессор, они вводят процессор в состояние, в котором он не может выполнить ни одной инструкции, т.к. непрерывно происходят исключения, но разные исключения в зависимости от приготовленных данных - и таким образом процессор вычисляет!

Известно, что одной инструкции условного перехода по вычитанию (вычисли a = a-b, и если это меньше или равно нуля, перейди в c) достаточно для Тьюринг-полноты. В этом хаке такая инструкция симулируется с помощью последовательности page faults (от невозможности загрузить данные), которая заканчивается double fault (когда указатель на стек уменьшается ниже нуля).

Несколько более подробное объяснение - в этом комментарии.

Любопытно, что ни один существующий эмулятор x86 не мог правильно запустить этот хак, потому что он опирается на слишком извращенную конфигурацию контрольных таблиц, и на тонкие нюансы поведения процессора в этой извращенной конфигурации. В итоге они смогли подстроиться под эмулятор Bochs.

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

(c) http://avva.livejournal.com/2570893.html