7
$\begingroup$

This question already has an answer here:

I'm quite new to computability theory and would be interested in some examples of realistic programming tasks you could encounter when working as a C++ programmer that are not computable.

$\endgroup$

marked as duplicate by David Richerby, jmite, Rick Decker, Raphael Apr 7 '17 at 19:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ What kind of programmer? Compiler writers encounter very different challenges as far as computability theory is concerned than, say, people who write accounting software. I run into problems all the time where I have to ask myself "could a user write a simple program that causes the compiler to hang forever?" $\endgroup$ – Eric Lippert Apr 7 '17 at 18:10
  • $\begingroup$ By definition, no "programming task" can be for an uncomputable problem. $\endgroup$ – Raphael Apr 7 '17 at 19:03
  • 1
    $\begingroup$ Welcome to Computer Science! We don't have a strict policy for list questions, but there is a general dislike. Please note also this and this discussion; you might want to improve your question as to avoid the problems explained there. If you are not sure how to improve your question maybe we can help you in Computer Science Chat? $\endgroup$ – Raphael Apr 7 '17 at 19:04
  • $\begingroup$ Several such problems have been covered in detail on their own, e.g. fully optimizing compilers and dead code protection. Basically, most questions about semantic properties of programs are not decidable (cf Rice's theorem -- which is why these are easy to prove undecidable). As for the real world, just note that real computers have finite precision, so basically any physics problem is not computable, quite trivially so. $\endgroup$ – Raphael Apr 7 '17 at 19:08
  • $\begingroup$ In summary: the list you are asking for is (infinitely) long, so it's not very meaningful to try and create one. You'll be better served by understanding the concepts. $\endgroup$ – Raphael Apr 7 '17 at 19:08
10
$\begingroup$
  • Are there some inputs that make my program crash?

  • Can this object be freed (from memory) or can it be needed later?

  • I'm building an editor and want to detect the programming language automatically. Given two languages described by CFGs, is there some input code for which I won't be able to guess the language (because it's valid in both languages)?

  • Do these two programs do the same thing?


Suppose that you have a property of programs so that:

  • It only depends on what the program does, not how it's written. So for example "It computes the factorial" or "It loops forever" work, but neither"It's written using a for loop" nor "It uses 5 variables" do.
  • There is some program that has the property
  • There is some program that doesn't have the property

Then Rice's theorem tells you that you can't have a (meta-)program that looks at source code and tells you if the program it describes has the property.

(My first and last examples are instances of that theorem)

$\endgroup$
  • 1
    $\begingroup$ Related to the first point: is this program bug free?. Note that this is a different question from what are the possible bugs in this program which is what compilers and linters do but what most people miss is that this is the best we can ever do $\endgroup$ – slebetman Apr 7 '17 at 17:55
  • 2
    $\begingroup$ Do you mean fulfill over verify? $\endgroup$ – cat Apr 7 '17 at 17:58
  • $\begingroup$ "that verifies the property" -- should be "has". $\endgroup$ – Raphael Apr 7 '17 at 19:09
1
$\begingroup$

Another uncomputable function that would be useful is one that compresses any data into a shortest possible description of it.

$\endgroup$

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