1
$\begingroup$

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!

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ This question seems to have infinitely many trivial answers (in fact, you basically answer your own question), so I'm not quite sure you have written down clearly what you'd like to see. Community votes? $\endgroup$ – Raphael♦ Feb 24 '15 at 22:39
  • $\begingroup$ Hi Raphael. I'm not sure how to make my question more precise, because I don't want to restrict the space of answers. So what I'll try to do is to put the question in a discursive way that should encourage some answers rather than others: Let's say that I want to convince a fellow computer scientist that computers are not all-powerful machines, but there are problems and phenomena that - fundamentally- lie 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? $\endgroup$ – Giovanni Sirio Carmantini Feb 25 '15 at 9:48
  • $\begingroup$ I am not sure chaos is a proper answer, as I suspect it can be approximated arbitrarily well (and arbitrarily slowly) by a TM. I would expect that one can study Chaos theory in the context of computable reals. So not even that would qualify ... unless you want to take into account quantum fluctuations. But then the real issue is the modelization of quantum non-determinism (which is far beyond my competence). So the real issue is possibly to define what you are calling a problem. $\endgroup$ – babou Feb 25 '15 at 10:36
  • $\begingroup$ Hi Babou. It is true that chaos can be approximated arbitrarily well, but I'll still never get the non-periodicity property and also, no matter how good my approximation is, the main quality of chaos is that the error explodes fast. So let's say that if my problem was something like "find an algorithm that, given an initial condition with a set precision, is able to accurately predict the behaviour of my chaotic system arbitrarily far in the future", then I could say that such an algorithm just doesn't exist. No computer can solve this problem, no matter how powerful. $\endgroup$ – Giovanni Sirio Carmantini Feb 25 '15 at 10:56
  • 1
    $\begingroup$ @GiovanniSirioCarmantini The thing is, no computer scientist with their head screwed on the right way would even argue with your point. Hence, asking for any example is both pointless and too broad for this platform. (SE does not take well to discourse, as you put it.) $\endgroup$ – Raphael♦ Feb 25 '15 at 11:21
2
$\begingroup$

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 https://mathoverflow.net/questions/54820/physics-and-church-turing-thesis

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I would upvote you, but I don't have enough reputation to do so. But thank you! $\endgroup$ – Giovanni Sirio Carmantini Feb 25 '15 at 19:49
  • $\begingroup$ The issue with chaotic systems is one of the effect of perturbations on approximate solutions. An one does not have to get to differential equations to illustrate that. Even a banal system of linear equations has a notion of condition number, which is an intrinsic measure of the instability of the problem's solution to perturbations in input. $\endgroup$ – SX welcomes ageist gossip Feb 26 '15 at 7:01
  • $\begingroup$ Another thing worth saying about chaos theory is that formal proofs of chaotic behavior are often very difficult and require a computer's assistance; this type of proof, relying on interval arithmetic should not be confused with simulations of dynamic systems using approximate representations. For example, the proof of the long-standing conjecture on the existence of a Lorenz strange attractor was done precisely this way by Tucker. $\endgroup$ – SX welcomes ageist gossip Feb 26 '15 at 7:13
-1
$\begingroup$

it is known some problems in theoretical physics are undecidable. have not found a nice simple list/ survey. see eg these two refs.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.