Solving Three Open Problems with a Halting Oracle

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

-
This still needs an objective scoring criteria. Also, proving that the pseudo-program works might be really challenging. – Mr. Llama Sep 6 '12 at 19:41
I said fewest characters. It's a codegolf problem. – dspyz Sep 6 '12 at 21:06
That is an, interesting, scoring procedure for this problem. "Solve the twin prime conjecture in the fewest number of characters." – PyRulez Mar 8 '14 at 16:16
man, what a cool question – undergroundmonorail Dec 25 '14 at 7:57

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.

-
So, does it support arbitrary precision after all? I think the prime test is easily fixable like the APL answer. – jimmy23013 Dec 31 '14 at 4:39
Since I already wrote that in the bounty criteria (for CJam), I think I'll follow the rules and award the Haskell answer... But +1 from me. – jimmy23013 Jan 1 '15 at 6:30

``````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.

-
Would you mind posting an ungolfed version of this as well? (with proper spacing and some type signatures) I didn't know you could put the bars all on one line like you did for c – dspyz Dec 24 '14 at 19:24
Shouldn't the primality tester go from [2..n-1]? (otherwise everything's composite) – dspyz Dec 24 '14 at 19:34
oh, also, does p test for primality or compositeness? – dspyz Dec 24 '14 at 19:37
I like the natural extension to haskell: h1 determines whether the evaluation of this thunk will halt, or better yet, h1 returns True for all computations that are not _|_ where it returns False (unless the computation uses h1 in which case the result itself is _|_). – dspyz Dec 24 '14 at 19:44
@dspyz hmm. that's nice. but that would allow us to abuse the fact that exceptions are bottoms, and that h1 throws exceptions when it is improperly used... I wonder how useful would that actually be. – proud haskeller Dec 24 '14 at 20:01

Python (965 characters)

Since my question is getting no love. I'm posting my (non-code-golfed) solution in Python:

``````def numCollatzSteps(n):
numSteps=0
while n>1:
if n%2==0:
n//=2
else:
n=3*n+1
numSteps+=1
return numSteps

def findNonHaltingN():
for n in count(1):
if not h1(numCollatzSteps,n):
return n

print "The Collatz Conjecture is "+str(not h2(findNonHaltingN))

def isPrime(n):
for i in range(2,n):
if n%i==0:
return False
else:
return True

def isSumOf2Primes(n):
for i in range(2,n-2):
if isPrime(i) and isPrime(n-i):
return True
else:
return False

def findNonSum():
for i in count(4,2):
if not isSumOf2Primes(i):
return i

print "Goldbach's Conjecture is "+str(not h1(findNonSum))

def isSmallTwinPrime(n):
return isPrime(n) and isPrime(n+2)

def nextSmallTwinPrime(n):
for i in count(n):
if isSmallTwinPrime(i):
return i

def largestTwinPrimes():
for n in count(2):
if not h1(nextSmallTwinPrime,n):
return n-1,n+1

print "The Twin Primes Conjecture is "+str(not h2(largestTwinPrimes))
``````

It's fairly simple.

numCollatzSteps(n) says how many steps the Collatz sequence for a particular n takes. It runs on infinitely if said Collatz sequence doesn't terminate.

findNonHaltingN() counts upwards checking that numCollatzSteps terminates for every n. findNonHaltingN terminates if and only if there exists an n for which numCollatzSteps does not terminate.

So we can check if the Collatz conjecture is true by checking that findNonHaltingN() does not halt

isPrime(n) checks if a number is prime by seeing that no positive integer from 1 to n-1 divides it

isSumOf2Primes(n) iterates over all positive integers between 2 and n-2 and checking that at least one is prime together with its complement

findNonSum() counts even numbers upwards from 4 until it reaches the first number which is not a sum of 2 primes and then returns it. If no such number exists, then it will continue infinitely.

We can check if Goldbach's conjecture is true by seeing that findNonSum does not halt.

isSmallTwinPrime(n) returns true if and only if n and n+2 are both prime

nextSmallTwinPrime(n) returns the next number >= n for which isSmallTwinPrime is true

largestTwinPrimes() counts upwards from 2 checking that nextSmallTwinPrime halts for all n. If ever nextSmallTwinPrime does not halt for some n, then it follows that the largest twin primes are n-1 and n+1 and we stop there

Then we can check the validity of the twin primes conjecture by checking that largestTwinPrimes never halts.

-

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]
``````
-
But does APL support big integers? – jimmy23013 Dec 25 '14 at 16:52
@user23013: In theory, APL's number format is an arbitrary-precision float, thus, in theory it can store any number. Of course, in practice, there is a limit, but it is implementation-dependent, and the question says to assume it can handle numbers of arbitrary size. – marinus Dec 26 '14 at 2:56
The question says only big integers can be arbitrarily large. – jimmy23013 Dec 26 '14 at 4:23
@user23013: it only has the one number type – marinus Dec 26 '14 at 16:29
Big integers usually means arbitrary precision integers. As clarified in the question, it should be able to express `3**(3**10)` (`3*3*10` in APL), which gives a DOMAIN ERROR in tryapl.org. – jimmy23013 Dec 26 '14 at 16:43