X-machines and the halting problem: Building a super-turing machine |
| |
Authors: | Mike Stannett |
| |
Affiliation: | (1) Formal Methods Group, Sheffield University, Sheffield, UK |
| |
Abstract: | We describe a novel machine model of computation, and prove that this model is capable of performing calculations beyond the capability of the standard Turing machine model. In particular, we demonstrate the ability of our model to solve the Halting problem for Turing machines. We discuss the issues involved in implementing the model as a physical device, and offer some tentative suggestions. |
| |
Keywords: | Computability Turing machine Super-Turing Halting problem X-machine |
本文献已被 SpringerLink 等数据库收录! |
|