Systematic listing of all possible programs

From apm
Revision as of 11:35, 11 June 2023 by Apm (Talk | contribs) (→‎(In)efficiency: added note on number systems)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

These are the first elements of the infinite list of
all programs that can be constructed with Turing complete formalism/machine.
Manually systematically constructed.
For an attempt in automating this construction (and subsequent cantor diagonal execution) see page:
The program of all programs (code)

Pick any phenomenon encountered in nature.
There should be a program that describes/models/simulates it
to any desired accuracy (non infinite accuracy).
In a sense it's a true theory of everything but maximally useless.
See: A true but useless theory of everything

An issue is true randomness in quantum randomness.
Only very global hidden variables could save hyper-determinism as
local hidden variables have been experimentally excluded over cosmic distances by now 2023 supposedly.
(wiki-TODO: find and link paper)

(In)efficiency

To state the obvious: This is not efficient.
In fact this is perhaps even a suitable definition for the maximal possible inefficiency.
On the other hand this "library of Babel of code" also contains the most efficient and ingenious algorithms possible.

It is well known that (unary and thus very inefficient) Chruch numerals are encodable in lambda calculus. But so are binary numbers and any kind of number system that one can and can't imagine. Plus all sorts of ootimized implementations.

This is based on lambda calculus.
There are alternate equally powerful minimal calculi (e.g. SKI calculus) that are
more efficient for some problems than the lambda calculus and less efficient for others.
Though one will find simulations of these other calculi withing the lambda calculus.

I leave thinking about how this goes together with quantum computing to the reader for now.

Manual systematic exhaustive code construction

Basic building blocks for an expression exp:

  • λ(exp)
  • @(exp)(exp)
  • I

Where I is an de Brujin indices with the additional constraint to be bound as a local variable.

The root can't be a de Brujin index variable because it would have no parent λ and thus would be unbound.
We don't want to allow for such unbound variables as then we'd need to count up to infinity λ0, λ1, λ2, λ3, …
The root can be an @ on the condition that both of it's branches need to contain a λ as a sort of sub-root with same rules applying as for the root.
The root can be be a λ as filling al remaining slots in expressions is always possible then.

The very fist and simple-most expression is the identity function
λ0 (or λx.x using a name).
Yes, most of the these expressions can't execute a single execution step.
They can be seen as final result values for eventual higher computations that eventually halt. Actually one needs to do the evaluation steps in cantor triangular fashion to be able to continue with term construction. Net yet reached the point where this becomes relevant here in this listing for now.

  • ID … argument stays unchanged (identity)
  • IG … argument gets ignored … note the de Brujin index remapping
2
λ0

3
λ(λ0)
λ(λ1)

4
λ(λ(λ0))
λ(λ(λ1))
λ(λ(λ2))

5
λ(λ(λ(λ0)))
λ(λ(λ(λ1)))
λ(λ(λ(λ2)))
λ(λ(λ(λ3)))
– – – – – 
@(λ0)(λ0) => λ0 ID

6
λ(λ(λ(λ(λ0))))
λ(λ(λ(λ(λ1))))
λ(λ(λ(λ(λ2))))
λ(λ(λ(λ(λ3))))
λ(λ(λ(λ(λ4))))
– – – – – – 
λ@(λ0)(λ0) => λ(λ0) ID
λ@(λ1)(λ0) => λ0 IG
λ@(λ0)(λ1) => λ(λ1) ID
λ@(λ1)(λ1) => λ0 IG
– – – – – –
@(λ(λ0))(λ0) => λ0 IG
@(λ(λ1))(λ0) => λ( λ0 ) SUBST
– – – – – –
@(λ0)(λ(λ0)) => λ(λ0) ID
@(λ0)(λ(λ1)) => λ(λ1) ID

7
λ(λ(λ(λ(λ(λ0)))))
λ(λ(λ(λ(λ(λ1)))))
λ(λ(λ(λ(λ(λ2)))))
λ(λ(λ(λ(λ(λ3)))))
λ(λ(λ(λ(λ(λ4)))))
λ(λ(λ(λ(λ(λ5)))))
– – – – – – – 
λ(λ@(λ0)(λ0)) => λ(λ(λ0) ID
λ(λ@(λ1)(λ0)) => λ(λ0) IG
λ(λ@(λ2)(λ0)) => λ(λ1) IG
λ(λ@(λ0)(λ1)) => λ(λ(λ1) ID
λ(λ@(λ1)(λ1)) => λ(λ0) IG
λ(λ@(λ2)(λ1)) => λ(λ1) IG
λ(λ@(λ0)(λ2)) => λ(λ(λ2) ID
λ(λ@(λ1)(λ2)) => λ(λ0) IG
λ(λ@(λ2)(λ2)) => λ(λ1) IG
– – – – – – – 
λ@(λ(λ0))(λ0) => λ(λ0) IG
λ@(λ(λ1))(λ0) => λ(λ( λ0 )) SUBST
λ@(λ(λ2))(λ0) => λ(λ1) IG
λ@(λ(λ0))(λ1) => λ(λ0) IG
λ@(λ(λ1))(λ1) => λ(λ( λ1 )) SUBST
λ@(λ(λ2))(λ1) => λ(λ1) IG
– – – – – – – 
λ@(λ0)(λ(λ0)) => λ(λ(λ0)) ID
λ@(λ0)(λ(λ1)) => λ(λ(λ1)) ID
λ@(λ0)(λ(λ2)) => λ(λ(λ2)) ID
λ@(λ1)(λ(λ0)) => λ0 IG
λ@(λ1)(λ(λ1)) => λ0 IG
λ@(λ1)(λ(λ2)) => λ0 IG
– – – – – – – 
@(λ(λ(λ0)))(λ0)) => λ(λ0) IG
@(λ(λ(λ1)))(λ0)) => λ(λ1) IG
@(λ(λ(λ2)))(λ0)) => λ(λ (λ0) ) SUBST
– – – – – – – 
@(λ(λ0))(λ(λ0)) => λ0 IG
@(λ(λ1))(λ(λ0)) => λ(λ (λ0) ) SUBST
@(λ(λ0))(λ(λ1)) => λ0 IG
@(λ(λ1))(λ(λ1)) => λ(λ (λ1) ) SUBST
– – – – – – – 
@((λ0)(λ(λ(λ0)))) => (λ(λ(λ0))) ID
@((λ0)(λ(λ(λ1)))) => (λ(λ(λ1))) ID
@((λ0)(λ(λ(λ2)))) => (λ(λ(λ2))) ID

8 (needs fixes)
λ(λ(λ(λ(λ(λ(λ0))))))
λ(λ(λ(λ(λ(λ(λ1))))))
λ(λ(λ(λ(λ(λ(λ2))))))
λ(λ(λ(λ(λ(λ(λ3))))))
λ(λ(λ(λ(λ(λ(λ4))))))
λ(λ(λ(λ(λ(λ(λ5))))))
λ(λ(λ(λ(λ(λ(λ6))))))
– – – – – – – – 
λ(λ(λ@(λ0)(λ0))) => λ(λ(λ(λ0) ID
λ(λ(λ@(λ1)(λ0))) => λ(λ(λ0) IG
λ(λ(λ@(λ2)(λ0))) => λ(λ(λ1) IG
λ(λ(λ@(λ3)(λ0))) => λ(λ(λ2) IG
λ(λ(λ@(λ0)(λ1))) => λ(λ(λ(λ1) ID
λ(λ(λ@(λ1)(λ1))) => λ(λ(λ0) IG
λ(λ(λ@(λ2)(λ1))) => λ(λ(λ1) IG
λ(λ(λ@(λ3)(λ1))) => λ(λ(λ2) IG
λ(λ(λ@(λ0)(λ2))) => λ(λ(λ(λ2) ID
λ(λ(λ@(λ1)(λ2))) => λ(λ(λ0) IG
λ(λ(λ@(λ2)(λ2))) => λ(λ(λ1) IG
λ(λ(λ@(λ3)(λ2))) => λ(λ(λ2) IG
λ(λ(λ@(λ0)(λ3))) => λ(λ(λ(λ3) ID
λ(λ(λ@(λ1)(λ3))) => λ(λ(λ0) IG
λ(λ(λ@(λ2)(λ3))) => λ(λ(λ1) IG
λ(λ(λ@(λ3)(λ3))) => λ(λ(λ2) IG
– – – – – – – – 
λ(λ@(λ(λ0))(λ0)) =>
λ(λ@(λ(λ1))(λ0)) =>
λ(λ@(λ(λ2))(λ0)) =>
λ(λ@(λ(λ3))(λ0)) =>
– – – – – – – – 
λ(λ@(λ(λ0))(λ1)) =>
λ(λ@(λ(λ1))(λ1)) =>
λ(λ@(λ(λ2))(λ1)) =>
λ(λ@(λ(λ3))(λ1)) =>
– – – – – – – – 
λ(λ@(λ(λ0))(λ2)) =>
λ(λ@(λ(λ1))(λ2)) =>
λ(λ@(λ(λ2))(λ2)) =>
λ(λ@(λ(λ3))(λ2)) =>
– – – – – – – – 
λ(λ@(λ0)(λ(λ0))) =>
λ(λ@(λ1)(λ(λ0))) =>
λ(λ@(λ2)(λ(λ0))) =>
– – – – – – – – 
λ(λ@(λ0)(λ(λ1))) =>
λ(λ@(λ1)(λ(λ1))) =>
λ(λ@(λ2)(λ(λ1))) =>
– – – – – – – – 
λ(λ@(λ0)(λ(λ2))) =>
λ(λ@(λ1)(λ(λ2))) =>
λ(λ@(λ2)(λ(λ2))) =>
– – – – – – – – 
λ(λ@(λ0)(λ(λ3))) =>
λ(λ@(λ1)(λ(λ3))) =>
λ(λ@(λ2)(λ(λ3))) =>
– – – – – – – – 
λ@(λ(λ(λ0)))(λ0) =>
λ@(λ(λ(λ1)))(λ0) =>
λ@(λ(λ(λ2)))(λ0) =>
λ@(λ(λ(λ3)))(λ0) =>
λ@(λ(λ(λ0)))(λ1) =>
λ@(λ(λ(λ1)))(λ1) =>
λ@(λ(λ(λ2)))(λ1) =>
λ@(λ(λ(λ3)))(λ1) =>
– – – – – – – – 
λ@(λ(λ0))(λ(λ0)) =>
λ@(λ(λ1))(λ(λ0)) =>
λ@(λ(λ2))(λ(λ0)) =>
λ@(λ(λ0))(λ(λ1)) =>
λ@(λ(λ1))(λ(λ1)) =>
λ@(λ(λ2))(λ(λ1)) =>
λ@(λ(λ0))(λ(λ2)) =>
λ@(λ(λ1))(λ(λ2)) =>
λ@(λ(λ2))(λ(λ2)) =>
– – – – – – – – 
λ@(λ0)(λ(λ(λ0))) =>
λ@(λ1)(λ(λ(λ0))) =>
λ@(λ0)(λ(λ(λ1))) =>
λ@(λ1)(λ(λ(λ1))) =>
λ@(λ0)(λ(λ(λ2))) =>
λ@(λ1)(λ(λ(λ2))) =>
λ@(λ0)(λ(λ(λ3))) =>
λ@(λ1)(λ(λ(λ3))) =>
– – – – – – – – 
@(λ(λ(λ(λ0))))(λ0) => λ(λ(λ0)) ignore
@(λ(λ(λ(λ1))))(λ0) => λ(λ(λ1)) ignore
@(λ(λ(λ(λ2))))(λ0) => λ(λ(λ2)) ignore
@(λ(λ(λ(λ3))))(λ0) => λ(λ(λ (λ0) ))
– – – – – – – – 
@(λ(λ(λ0)))(λ(λ0)) => λ(λ0) ignore
@(λ(λ(λ1)))(λ(λ0)) => λ(λ1) ignore
@(λ(λ(λ2)))(λ(λ0)) => λ(λ (λ(λ0)) )
– – – – – – – – 
@(λ(λ(λ0)))(λ(λ1)) => λ(λ0) ignore
@(λ(λ(λ1)))(λ(λ1)) => λ(λ1) ignore
@(λ(λ(λ2)))(λ(λ1)) => λ(λ (λ(λ1)) )
– – – – – – – – 
@(λ(λ0))(λ(λ(λ0))) => λ0 ignore
@(λ(λ1))(λ(λ(λ0))) => λ(λ (λ(λ(λ0))) )
@(λ(λ0))(λ(λ(λ1))) => λ0 ignore
– – – – – – – – 
@(λ(λ1))(λ(λ(λ1))) => λ(λ (λ(λ(λ1))) )
@(λ(λ0))(λ(λ(λ2))) => λ0 ignore
@(λ(λ1))(λ(λ(λ2))) => λ(λ (λ(λ(λ2))) )
– – – – – – – – 
@(λ0)(λ(λ(λ(λ0)))) => λ(λ(λ(λ0)))) id
@(λ0)(λ(λ(λ(λ1)))) => λ(λ(λ(λ1)))) id
@(λ0)(λ(λ(λ(λ2)))) => λ(λ(λ(λ2)))) id
– – – – – – – – 
@(λ0)(@(λ0)(λ0)) => @(λ0)(λ0) id

9
It might get more interesting here with two @s but
no way I would attempt systematic construction of 
the 9 element expressions manually ...


Related

Retrieved from "http://apm.bplaced.net/w/index.php?title=Systematic_listing_of_all_possible_programs&oldid=14809"