Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Машины мощнее машины Тьюринга

Hypercomputation: computing more than the Turing machine by Toby Ord 

Models of computation that compute more than the Turing machine are conceptually unproblematic and may even be buildable. This has many important implications. The most direct of these is that mathematical proofs that certain functions are ‘uncomputable’ must be more clearly understood as shorthand for ‘uncomputable by a Turing machine’ and not as a limitation on mathematics.

Hypercomputation clearly has considerable implications for computer science, yet it has received almost no attention there. Part of the reason for this is that few people realise that it is logically possible to exceed the power of the Turing machine. It is often believed that the Church-Turing Thesis rules out the possibility of hypercomputation. Another common misconception is that the proof of the uncomputability of the halting function by Turing machines makes it paradoxical for any machine to compute it. Finally, people dismiss the possibility of hypercomputation as completely unrealistic or in violation of some physical laws.

The first two of these reasons for ignoring the possibility of hypercomputation are simply false. The third would have some force if it was used with an understanding of the many different resources that could be used to achieve hypercomputation, but there has been no detailed analysis of whether these resources are physically realisable. It is thus very unfortunate that the reasons above have caused so many people to ignore the fascinating possibilities that hypercomputation offers.

One of the main reasons that people still hold these misconceptions is that the basic issues of hypercomputation – particularly those three just mentioned – are often not well understood and consequently the possibility of hypercomputation is not presented in textbooks or lectures. While there are exceptions to this (most notably brief presentations of O-machines), students still tend to finish their computer science education with a firm belief that the Turing machine has limits on its computation, but that it is as powerful (in terms of computability) as any other possible machine.
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 23 comments