What tools exist to compute all possible programs?

post by Alexei · 2019-09-09T16:50:57.162Z · score: 18 (4 votes) · LW · GW · No comments

This is a question post.

Contents

  Answers
    3 dyokomizo
    3 gilch
None
No comments

Are there tools / programs out there that try to compute and run all possible programs for some simple, custom language? Like something you might do if you were to naively run AIXI.

Answers

answer by dyokomizo · 2019-09-09T19:42:34.423Z · score: 3 (2 votes) · LW · GW

miniKanren is a logic/relational language. It's been used to solve questions related to programs. For example, once you give miniKanren a description of the untyped λ-calculus extended with integers you can ask it "give me programs that result in 2" and it'll enumerate programs from the constant "2" to "1 + 1" to more complicated versions using λ-expressions. It can even find quines (if the described language supports it).

http://minikanren.org/

answer by gilch · 2019-09-09T18:52:37.372Z · score: 3 (2 votes) · LW · GW

See https://en.m.wikipedia.org/wiki/Iota_and_Jot This is a way to enumerate all possible programs as binary numbers.

No comments

Comments sorted by top scores.