So here's the point: According to Godel's incompleteness theorem, ZFC can't prove that ZFC is consistent. https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_... But if ZFC could prove that this Turing machine never halts, it would prove its own consistency, so tada! we've put a hard upper bound on the complexity of problems that ZFC can deal with.
These particular Turing machines that were built, have special properties that allow them to test mathematical axioms/theorems, so for example, if the Z machine halts, then it means that the ZFC axioms are wrong. In the article, this is stated in the negative form ("Z will run forever if ZFC is right").
Disclaimer: it's been a long time since I last read the formal definitions of turing machines, and my explanation may be sloppy -- but I aimed for a more general thing to give you an idea.
At it's simplest a Turing machine consists of an infinite tape of memory cells, a read/write head, a state register, and a state transition table (functions). Read the current cell and look up the pair (current state, cell value) to get the effect (new cell value, direction to move head [left, right, stay], new state).
Nothing in real computers can't be translated to a Turing machine description. It just won't be efficient :P. And anything written for a Turing machine will run on a real computer, modulo memory available.
is_prime(n) {
for (i = 2; i < n; i++)
if (n % i == 0)
return false; // sorry, this isn't prime
return true; // no divisors found, prime
}
main() {
for (i = 4; ;i += 2) { // consider all even numbers i > 2
for (j = 2; j <= i-2; j++) { // consider i as the sum j + (i-j)
if (is_prime(j) && is_prime(i-j))
break; // both are prime, so i is a sum of two primes
}
if (j > i-2) // oops, we checked all js and nothing was found
return i; // i is an even number but not a sum of two primes
}
}
You can compile such program yourself and run it to see if it stops ;)Just remember to use some bignum library instead of plain ints.