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:

  • 1
    \$\begingroup\$ What is an example of an undecidable set? \$\endgroup\$
    – Doorknob
    Dec 8 '13 at 20:11
  • \$\begingroup\$ Added some examples. \$\endgroup\$ Dec 8 '13 at 20:18
  • \$\begingroup\$ "Programs of any Turing-complete language which halt." So that means we can output print(1+1), print(2+2), print(3+3), etc.? \$\endgroup\$
    – Doorknob
    Dec 8 '13 at 20:20
  • 2
    \$\begingroup\$ @Doorknob can you print every valid Python program that halts? \$\endgroup\$ Dec 8 '13 at 20:21
  • \$\begingroup\$ @JanDvorak Wait, so the set has to be finite, but it has to be impossible to test whether an element is in the set, but that's contradictory... set.indexOf(element) > -1 \$\endgroup\$
    – Doorknob
    Dec 8 '13 at 20:22

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
 let r=repeat z
 (p,q)<-zip r[1..z]++zip[1..z]r
 if gcd p q==1 then[p%q]else[]
o l=d[map(:xs)r|xs<-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[[]]
s([]:b)=s b
s((x:a):b)=[x]:z a(s 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 <- [1..]
  let r = repeat limit
  (p,q) <- 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 <- 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]] -> [a]
diagonal = concat . stripe
    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.


Haskell, 232 characters (with line breaks removed)

This Haskell program prints all solvable Post correspondence problems over the alphabet {A, B}. (Actually, it prints only the ones that actually use every tile at least once. But this shouldn't affect the undecidability of the set.) Each set of tiles is sorted (using Haskell's sort function; I don't know how that works on lists of tuples of strings, but it does) and de-duplicated (using nub), and the entire list of solutions is de-duplicated as well.

It works by generating all strings, and then, for each string and for each number n up to twice the length of the string plus one, generating all pairs of ways to break the string into n pieces. The d function generates all ways to break a string s into a number n of pieces. The program takes advantage of the fact that in Haskell, do notation on lists simulates non-deterministic choice.

(If I'm not mistaken, "twice the length of the string plus one" is the greatest number of distinct tiles a string can serve as a solution string for. For example, "AB" is a solution string for ("","A"), ("","B"), ("A",""), ("B",""), ("","").)

The sequence command, as used right after s <- (but not as used right after main =), returns all ways of selecting one element from each of a list of lists; for example, sequence ["abc", "123"] is ["a1", "a2", "a3", "b1", "b2", "b3", "c1", "c2", "c3"].

import Data.List;
main=sequence.map print.nub$do{
s<-sequence$replicate n"AB";
u<-d p (s*2+1);
v<-d p (s*2+1);
return.nub.sort$zip u v
d 0""=[[]];
d 0_=[];
d n s=do
f<-[0..length s];
c<-d(n-1)(drop f s);
return(take f s:c)

With the line breaks, this is 246 characters, but all of the line breaks can be removed.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.