Solving Three Open Problems with a Halting Oracle

Question

You are given the functions: h1(f,*args) and h2(f,*args)

Both are methods which are already defined for you (here the asterisk indicates a variable number of arguments)

f is a function, *args is a list of parameters to be passed to that function

h1 returns a boolean value: True if the function f ever halts when called on *args and False if it doesn't (assuming the machine running it has infinite time and memory and that the interpreter/compiler for the language you're writing in knows how to handle infinite time and memory).

If f(*args) would ever make a call to h1 or h2, h1 throws an exception

h2 behaves exactly like h1 except that if f makes calls to h1, then h2 will not throw an exception

In as few characters as possible, write a program which takes no input and should output:

The Collatz Conjecture is {True/False}
Goldbach's Conjecture is {True/False}
The Twin Primes Conjecture is {True/False}

based on the validity of each of those conjectures.

Here are wikipedia links explaining each of the conjectures:

http://en.wikipedia.org/wiki/Collatz_conjecture

http://en.wikipedia.org/wiki/Goldbach%27s_conjecture

http://en.wikipedia.org/wiki/Twin_prime

You may assume any big integer library in whatever language you choose to use will successfully represent arbitrary large integers. In other words, we'll assume any language/library which is capable of expressing 3**(3**10) is also capable of expressing 3**(3**(3**10)) on a sufficiently beefy machine.

Obviously since it's impossible to run your program, please provide an explanation of how it works along with the code

Answer 1

Haskell, 242

p n=and[rem n r>0|r<-[2..n-1]]
c 1=1
c n|odd n=c$3*n+1|0<1=c$div n 2
s!f=putStr(s++" Conjecture is ")>>print(not$h2$all(h1.f)[4..])
main=do"The Collatz"!c;"Goldbach's"! \n->or[p$n-r|r<-[2..n-2],p r];"The Twin Primes"! \n->or[p$r+2|r<-[n..],p r]

because in Haskell variables can contain not only values, but computations (this is called laziness) I let myself make h1, h2 take a single argument and return weather or not it's evaluation will halt.

somewhat ungolfed code:

h1 = undefined
h2 = undefined

prime n=and[rem n r>0|r<-[2..n-1]]
collatz 1=1
collatz n
    |odd n=collatz (3*n+1)
    |0<1  =collatz (div n 2)
    
s!f=do
    putStr (s++" Conjecture is ")
    print$not$h2$all(h1.f)[4..]
    
main=do
    "The Collatz"!c                                         --collatz
    "Goldbach's"! \n->or[prime (n-r)|r<-[2..n-2],prime r]   --goldbach
    "The Twin Primes"! \n->or[prime (r+2)|r<-[n..],prime r] --twin primes

a bit of explanation:

when all is applied to an infinite list, it will halt iff one of the elements of the list is False, due to laziness (short-circuiting, for all non-Haskell folks out there). we use this to compute the collatz conjecture and the twin primes conjecture.

! packages this trickery along with printing. the result is True when f terminates on all the numbers 4... (this doesn't matter for the collatz conjecture or the twin primes conjecture, because we already know they are true for such small numbers).

the code for the collatz conjecture is "The Collatz"!c. it prints "The Collatz Conjecture is " and the result, which is weather c terminates on all numbers 4...

the code for the goldbach conjecture is "Goldbach's"! \n->or[p$n-r|r<-[2..n-2],p r]. \n->or[p$n-r|r<-[2..],p r,r<n+1] is a function which given n, if it is a sum of two primes, returns True, but otherwise loops indefinitely. thus, if it halts for every 4.. goldbach's conjecture is true.

the code for the twin primes conjecture is "The Twin Primes"! \n->or[p$r+2|r<-[n..],p r]. \n->or[p$r+2|r<-[n..],p r] is a function which given n, if there are twin primes greater than n, returns True, but otherwise loops indefinitely. thus, if it halts for every 4.. the twin prime conjecture is true.

Answer 2

J, 207

(('The Collatz';'Goldbach''s';'The Twin Primes'),.<'Conjecture is'),.((>:^:((((-:`>:@*&3)^:(~:&1))^:_)&f)^:_ g 2)((+&2)^:(+./@1&p:@(-p:@_1&p:))^:_ f 4)(>:^:((4&p:)^:(2&~:&(-~4&p:))&f)^:_ g 3){'True':'False')

I chose to use f and g in place of h1 and h2, as according to the bounty; two additional lines with 10 total characters prior is sufficient to switch: f=:h1,g=:h2.

And the actual logic:

Collatz

>:^:((((-:`>:@*&3)^:(~:&1))^:_)&f)^:_ g 2

((-:`>:@*&3)^:(~:&1))^:_ is the meat of it; it's essentially a loop that does while (x != 1) x = collatz(x). If we call that sentence reduce:

>:^:(reduce&f)^:_ g 2

reduce&f is meant to be a monadic verb (see end), where reduce&f n is true iff reduce(n) halts. The other loop-y bits, >:^:()^:_, are essentially an infinite loop (>: is increment, ^: can be used as a conditional and an iterator) which breaks upon encountering a Collatz reduction that does not halt. Finally the g is called to see if the infinite loop ever terminates.

Goldbach

(+&2)^:(+./@1&p:@(-p:@_1&p:))^:_ f 4

The same logic, for the most part, the obvious difference being the core calculation is now +./@1&p:@(-p:@_1&p:). -p:@_1&p: calculates the difference between a number and all the primes less than that number, 1&p: is an isPrime function, and +./ is logical OR. Hence, if the difference between a number and any prime less than that number is also a prime, then the Goldbach conjecture is satisfied, and the infinite loop continues on. Again, f is used in a final test of whether said infinite loop is truly infinite.

Twin Primes

>:^:((4&p:)^:(2&~:@(-~4&p:))&f)^:_ g 3

Same as above, excepting (4&p:)^:(2&~:@(-~4&p:)). 4&p: returns the next largest prime after a given number. -~4&p: returns the difference between a number and the next largest prime after it. 2&~: is != 2. So the innermost loop is analogous to while (nextPrimeAfter(p) - p != 2) p = nextPrimeAfter(p).

Notes

There may be syntactical errors, since I haven't tested with dummy f and g yet. Also, I assumed that f and g would take some sort of form that can be composed with a verb on the left and a noun on the right, which I'm not completely sure adheres to the J grammar in any way. They're inherently higher order functions, and I'm too tired to look up a proper construction as adverbs/conjunctions/what-have-you at the moment, if there even is such an appropriate construct.

I didn't really use proper string concatenation, and instead opted to leave individual strings boxed. The output (assuming all else is correct) would therefore be a 3 column table, with the left column being "The Collatz", etc., the middle column being "Conjecture is", and the right column "True"/"False".

I'm also pretty sure J doesn't convert integers to arbitrary precision by default, and the crucial prime number utility function p: does not have an arbitrarily large domain. On the other hand, given that J does support a standard arbitrary precision number type, I'm not sure how much effort it'd take to get this code up to par.

Answer 3

APL (234)

It's obviously untested, but the logic seems sound. Printing commands are all included, the output is 104 characters and the actual logic is 130.

Z←' Conjecture is '∘,¨'True' 'False'
⎕←'The Collatz',Z[1+{~{1=⍵:⍬⋄2|⍵:∇1+3×⍵⋄∇⍵÷2}h1⍵:⍬⋄∇⍵+1}h2 1]
⎕←'Goldbach''s',Z[1+{~⍵∊∘.+⍨N/⍨~N∊∘.×⍨N←1+⍳⍵:⍬⋄∇⍵+2}h1 2]
⎕←'The Twin Primes',Z[1+{~(T←{∧/{2=+/(⌈=⌊)⍵÷⍳⍵}¨N←⍵+1:N⋄∇N})h1⍵:⍬⋄∇T⍵}h2 4 2]

Ungolfed:

⍝ Environment assumptions: ⎕IO=1 ⎕ML=1
⍝ I've also assumed h1 and h2 are APL operators
⍝ i.e. x F y = f(x,y); x (F h1) y = h1(F,x,y)

⍝ 'Conjecture is True', 'Conjecture is False'
Z←' Conjecture is '∘,¨'True' 'False'

⍝⍝⍝ Collatz Conjecture
⍝ halts iff 1 is reached from given ⍵
collatzLoop←{
   1=⍵:⍬       ⍝ ⍵=1: halt
   2|⍵:∇1+3×⍵  ⍝ ⍵ uneven: loop with new val
   ∇⍵÷2        ⍝ ⍵ even: loop with new val
}

⍝ halts iff 1 is *not* reached from a value ≥ ⍵ (collatz false)
collatzHalt←{~collatzLoop h1 ⍵:⍬⋄∇⍵+1}

⍝ does it halt?
⎕←'The Collatz',Z[1+ collatzHalt h2 1]


⍝⍝⍝ Goldbach's Conjecture

⍝ Can ⍵ be expressed as a sum of two primes?
sumprimes←{
    N←1+⍳⍵         ⍝ N=[2..⍵+1]
    P←(~N∊N∘.×N)/N ⍝ P=primes up to ⍵+1×⍵+1
    ⍵∊P∘.+P        ⍝ can two P be summed to ⍵?
}

⍝ halts iff Goldbach is false
goldbachHalt←{
    ~sumprimes ⍵:⍬ ⍝ not a sum of primes: halt
    ∇⍵+2           ⍝ try next even number
}

⍝ does it halt?
⎕←'Goldbach''s',Z[1+ goldbachHalt h1 2]

⍝⍝⍝ Twin Primes

⍝ is it a prime?
isPrime←{
   2=+/(⌊=⌈)⍵÷⍳⍵    ⍝ ⍵ is a prime if ⍵ is divisible by exactly two
                   ⍝ numbers in [1..⍵] (i.e. 1 and ⍵)
}

⍝ find next twin
nextTwin←{
   N←⍵+1            ⍝ next possible twin
   ∧/ isPrime¨ N:N  ⍝ return it if twin
   ∇N               ⍝ not a twin, search on
}       

⍝ halts iff no next twin for ⍵
twinPrimeHalt←{
   ~nextTwin h1 ⍵: ⍬  ⍝ if no next twin for ⍵, halt
   ∇nextTwin ⍵        ⍝ otherwise try next twin
}

⍝ does it halt?
⎕←'The Twin Primes',Z[1+ twinPrimeHalt h2 4 2]