If you want to make money online : Register now

[Solved]: Examples of processes / problems that cannot be tackled by Turing Machines

, , No Comments
Problem Detail: 

I know that there are problems that cannot be solved by any algorithm, such as the Halting problem. I also know that some processes cannot be even adequately approximated by any Turing Machine (equivalently, any digital computer), meaning that some property of the process cannot be simulated due to its intrinsic nature. An example of this would be Chaos, and its non-periodicity.

My question is: are there any other interesting processes in nature that really are outside the realm of what Turing Machines / digital computers can tackle? Any other interesting problems (outside from the well-known textbook ones) that Turing Machines cannot solve?

The reason why I ask for this is that I'm teaching to computer science students, and I want to make sure they understand that computers are not all-powerful machines, but there are problems and phenomena that lie fundamentally outside the realm of possibilities of any digital computer. What powerful examples could I use, other than Chaos and the Halting problem, to support my argument?

Thank you!

Asked By : Giovanni Sirio Carmantini

Answered By : Fizz

I'll address as answer only part of the question (see my comments for why not all of it). The interesting phylosophical part of the question is basically asking if the Church-Turing thesis (CTT) describes all that happens in the universe. This is much more a physics question than it really is a CS question. CTT has been extended to the Church–Turing–Deutsch principle to account for quatum computers; it basically states that a quantum computer can simulate any physical process in the universe.

So what about continuous processes that we normally model over $\mathbb{R}$? Well, there are two aspects of this:

  • Models of computation with infinite-precision real-numbers have been devised. Whether you think such a model is the "right" one for physical processes, depends on physics and...
  • There are tough issues like the Bekenstein bound, which limit the amount of information that can exist in a finite region of space as we currently understand it. For details on this latter issue, it's much better to ask on our physics sister site.

A bit more info with pointer to additional readings is found at http://mathoverflow.net/questions/54820/physics-and-church-turing-thesis

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/39768

 Ask a Question

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback