Enumerate an undecidable set An undecidable set is a set for which determining whether an object is an element of the set is an undecidable problem

Write a program which runs forever, printing the elements of any undecidable set, each element appearing on its own line.  For any element in the set, there must be a finite amount of time after which your program will print that element.  Each element should only be printed once.

Since you have to enumerate the elements, the set you choose will be RE.

Some examples of undecidable sets which are RE:


Programs of any Turing-complete language which halt.
Post correspondence problem instances with solutions.  
Sets of Wang tiles which can't tile the plane.
Haskell, 404 characters

This Haskell program prints all FRACTRAN programs which halt when given the input 2. (The syntax of a FRACTRAN program is a list of positive rational numbers.)

import Data.Ratio
import Data.List
import Data.Either
r=do
 z&lt;-[1..]
 let r=repeat z
 (p,q)&lt;-zip r[1..z]++zip[1..z]r
 if gcd p q==1 then[p%q]else[]
o l=d[map(:xs)r|xs&lt;-l]
e p n=n:maybe[](e p)(find((==1).denominator)$map(*n)p)
h p=map Left(e p 2)++[Right p]
main=mapM print$rights$d$map h$d$iterate o[[]]
d=concat.s
s[]=[]
s([]:b)=s b
s((x:a):b)=[x]:z a(s b)
z[]b=b
z a[]=map(:[])a
z(x:a)(y:b)=(x:y):z a b


I have made no great effort to compress this program. Furthermore, the GCD test in the definition of r is purely an optimization (it avoids duplicates).

(Also, If you are interested in running it, be sure to compile it, perhaps with optimization; I found that running it in ghci quickly consumed gigabytes of memory.)

It operates by successively constructing infinite lists of infinite lists and then flattening them in a diagonal order: the list of all positive rational numbers, the list of all lists of positive rational numbers (all programs), and the list of all evaluation states (including “halted”) of all programs. We then print only the halted states (which are annotated with the program which halted).

Here is the uncompressed and commented version:

import Data.Ratio
import Data.List
import Data.Either

-- List of all positive rational numbers
rationals = do
  limit &lt;- [1..]
  let r = repeat limit
  (p,q) &lt;- zip r [1..limit] ++ zip [1..limit] r
  if gcd p q == 1 then [p%q] else []
-- List of all lists of positive rational numbers (all FRACTRAN programs)
programs = diagonal $ iterate oneMore [[]]
oneMore l = diagonal [map (:xs) rationals | xs &lt;- l]

-- FRACTRAN evaluator
evalStep p n = find ((== 1) . denominator) $ map (* n) p
evaluation p n = n : maybe [] (evaluation p) (evalStep p n)
evaluationWithHaltMarker p = map Left (evaluation p 2) ++ [Right p]

-- All evaluation states of all programs
evaluations = diagonal $ map evaluationWithHaltMarker programs

-- All halting programs
haltingPrograms = rights evaluations

main = mapM_ print haltingPrograms

-- from http://stackoverflow.com/questions/7141287/haskell-cartesian-product-of-infinite-lists
diagonal :: [[a]] -&gt; [a]
diagonal = concat . stripe
    where
    stripe [] = []
    stripe ([]:xss) = stripe xss
    stripe ((x:xs):xss) = [x] : zipCons xs (stripe xss)

    zipCons [] ys = ys
    zipCons xs [] = map (:[]) xs
    zipCons (x:xs) (y:ys) = (x:y) : zipCons xs ys


The Left values are never actually looked at since we don't care about non-halting states; it's just the shortest way I saw to carry through the incremental evaluation.

Some “future work” if one were trying to write a practical implementation to generate interesting programs, rather than golfing, would be to reduce the needed work by restricting the set of programs under consideration to those which:


do not have a statically obvious loop (e.g. an integer).
are unique under “register renaming”; e.g. [3/2, 5/3] is the same as [7/2, 5/7].
have no dead code under the assumption that the input is 2; e.g. in [5/3, 7/2], 5/3 is dead code because no 3s are in numerators.
have no dead code due to preceding code; e.g. in [3/2, 5/2], 3/2 will always take precedence over 5/2.


I mention these cases in particular because (other than the looping one) they form the majority of the output. As far as I've run it, it has not produced any output program of length greater than 2.