7
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 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, 2017 at 18:10
  • $\begingroup$ By definition, no "programming task" can be for an uncomputable problem. $\endgroup$
    – Raphael ♦
    Apr 7, 2017 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, 2017 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, 2017 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, 2017 at 19:08

2 Answers 2

Reset to default
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)

Improve this answer
$\endgroup$
3
  • 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, 2017 at 17:55
  • 2
    $\begingroup$ Do you mean fulfill over verify? $\endgroup$
    – cat
    Apr 7, 2017 at 17:58
  • $\begingroup$ "that verifies the property" -- should be "has". $\endgroup$
    – Raphael ♦
    Apr 7, 2017 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.

Improve this answer
$\endgroup$

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