This repo contains Enigma webapp demonstrating enumeration of all possible terminating programs (index.html).
Abstract machine has sum, diff and times (dynamically aka dependently bounded recursion) operations making it computationally complete.
Static termination check: DAG means terminating program.
Static memoization ensures no equivalent algorithms are enumerated.
Simplicity control (to be improved): from simplest to most complex programs, thus from simplest to most complex outputs.
Security applications:
- this, in theory, is attack on one-time pad. Shannon's fundamental assumption of uniformity is rejected:
- output, that is easiest to compute with "no-input" program that is easiest to find, has higher probability of appearance
- true random is defined as "hardest to compute from known numbers, up to security threshold"
- for a given security threshold (e.g. minimum 100Kwh energy spent on computation) amount of resources needed to actually satisfy it is more than threshold itself and unpredictable: spending nominal amount does not guarantee the number will be unique. E.g. no planned economy can satisfy true randomness.
Enigma will be a reference deterministic TRNG for https://doomsdayexplorer.online defense network.
Shannon's entropy only applicable in cases where the whole set of events under consideration is already fully computed, stored and readily accessible, as well as selection procedure, which is not the case in security. Shannon's entropy is loosely applicable to pseudo-random generation (lottery, coin-toss), which is not applicable in security: e.g. outcome of a coin-toss is predictable from initial state and distance traveled:
(init + distance) mod 2, slight periodic change of initial state and distance gives illusion of randomness.
Test cases:
Enigma has DSL for test cases.
Additionally, trng.html contains typical TRNG replica, abstracting from physical parameters.
Enigma is expected to find this replica fast, given proper simplicity control.
P.S. No AI was used to write the apps.
Layman explanation:
Number 3 appears in nature more often than 198394838854. Shannon, however, assumed same likelihood.
Size of a number is not necessarily important. 300000000, 3232323232 have similar high likelihood of appearance with 3, while 285759 is much less likely.
What important is how hard is to find a way to create number and how hard is it to create it.