13 ms·

This is the first time I feel like I missed out on something by not taking Theory of Computation in college. Anyone care to break down what this article is talk

This is the first time I feel like I missed out on something by not taking Theory of Computation in college. Anyone care to break down what this article is talking about?

ggggtez 10y ago
They are playing code golf to explain how complicated a math problem is. The lower the number of states, the "easier" it is.
Mithaldu 10y ago
Yeah, this really needs an explanation of what is different about it compared to ... while(1){ sleep 1; }
- qb45 10y ago
  They just look for counterexamples. Say, for Goldbach: 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.
  - Mithaldu 10y ago
    That is maybe not the most accurate example, but it is amazingly simple and gets the idea across. Thank you. :)
dr_zoidberg 10y ago
A turing machine is a mathematical abstraction that is the simplest machine that can compute things. Due to it's nature of "mathematical abstraction", it's actually impossible to build one, though you can restrict it and build one of course. In particular, we have real computers (more complex than Turing machines, and with other restrictions). 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.
- Jtsummers 10y ago
  Really the only thing preventing the construction of a true Turing machine is the inability to have an infinitely long tape. Fortunately, that limitation isn't a problem in practice for most things you'd wish to compute. 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.
sp332 10y ago
The link davesque posted goes into a lot more detail, but here's a short version. They created a Turing machine that encodes a set of axioms known as ZFC https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_t... The Turing machine just enumerates every single possible assertion using those axioms and tests them for consistency. If it ever proves, say, 1+1=3 then it will halt. 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_theorems#First_incompleteness_theorem 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.

This is the first time I feel like I missed out on something by not taking Theory of Computation in college. Anyone care to break down what this article is talking about?

ggggtez 10y ago

They are playing code golf to explain how complicated a math problem is. The lower the number of states, the "easier" it is.

Mithaldu 10y ago

Yeah, this really needs an explanation of what is different about it compared to ... while(1){ sleep 1; }

qb45 10y ago
They just look for counterexamples. Say, for Goldbach: 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.
- Mithaldu 10y ago
  That is maybe not the most accurate example, but it is amazingly simple and gets the idea across. Thank you. :)

dr_zoidberg 10y ago

A turing machine is a mathematical abstraction that is the simplest machine that can compute things. Due to it's nature of "mathematical abstraction", it's actually impossible to build one, though you can restrict it and build one of course. In particular, we have real computers (more complex than Turing machines, and with other restrictions). 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.

Jtsummers 10y ago
Really the only thing preventing the construction of a true Turing machine is the inability to have an infinitely long tape. Fortunately, that limitation isn't a problem in practice for most things you'd wish to compute. 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.

sp332 10y ago

The link davesque posted goes into a lot more detail, but here's a short version. They created a Turing machine that encodes a set of axioms known as ZFC https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_t... The Turing machine just enumerates every single possible assertion using those axioms and tests them for consistency. If it ever proves, say, 1+1=3 then it will halt. 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_theorems#First_incompleteness_theorem 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.