News for hackers. Stuff that matters.
Re:Turing machines that should run forever by alistproducer2 on Wednesday May 11, 2016 @12:58PM (#11677016)
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?
Re:Turing machines that should run forever by ggggtez on Wednesday May 11, 2016 @01:27PM (#11677265)
They are playing code golf to explain how complicated a math problem is. The lower the number of states, the "easier" it is.
Re:Turing machines that should run forever by sp332 on Wednesday May 11, 2016 @01:54PM (#11677580)
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_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_... 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.

Re:Turing machines that should run forever by dr_zoidberg on Wednesday May 11, 2016 @01:39PM (#11677434)
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.

Re:Turing machines that should run forever by Jtsummers on Wednesday May 11, 2016 @01:51PM (#11677553)
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.

Re:Turing machines that should run forever by Mithaldu on Wednesday May 11, 2016 @01:28PM (#11677281)
Yeah, this really needs an explanation of what is different about it compared to ... while(1){ sleep 1; }
Re:Turing machines that should run forever by qb45 on Wednesday May 11, 2016 @03:27PM (#11678455)
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.

Re:Turing machines that should run forever by Mithaldu on Wednesday May 11, 2016 @03:34PM (#11678514)
That is maybe not the most accurate example, but it is amazingly simple and gets the idea across. Thank you. :)