Αναρτήσεις

Προβολή αναρτήσεων από Νοέμβριος, 2012

Super-recursive algorithms

It seems that some people do not understand the connection between hypercomputation and what Mark Burgin calls super-recursive algorithms. According to Burgin, "super-recursive algorithms are algorithms that control hypercomputation." In different words, a method that describes a task that produces a result not computable by a Turing machine is a super-recursive algorithm (or a hyperalgorithm, as I like to call them).

Will my program terminate?

Roughly speaking, Turing has proved that it is not possible to tell whether a computer program will terminate or not. Recently, William Gasarch posted an article to the arXiv in which he shows how one can prove program termination. Gasarch does not disprove Turing, but " discuss various ways to prove that [a] program terminates".