3
$\begingroup$

Is there a real world nonmathematical example of computer software that isn't primitive recursive?

I'm not interested in examples that are somehow closely related to theory of computation or logic (like automated theorem proving, model checking, compiler design etc.), or examples that aren't primitive recursive in a trivial way (i.e. having unbounded loops that could have been bounded).

The example doesn't have to be an actually existing piece of code (although it would be great if it is).

$\endgroup$
  • $\begingroup$ A function is (or isn't) primitive recursive, according to a given formal definition. By "non-mathematical" you mean that it would be a mathematical definition hidden in an algorithm that would have appeared spontaneously on a computer application in the "real world", not out of some theoretical or arbitrary exercise? $\endgroup$ – André Souza Lemos Sep 18 '16 at 21:49
  • $\begingroup$ Yes. By "non-primitive recursive software" I mean "software that implements a non-trivial non-primitive recursive function". I'm aware of some examples of this that reduce to undecidability of certain logical systems; but I'd like a more natural example. $\endgroup$ – Luka Mikec Sep 18 '16 at 21:59
  • $\begingroup$ These are hard problems that usually demand mathematical treatment, even if a posteriori. You are looking for a raw diamond in the desert. Tough call. $\endgroup$ – André Souza Lemos Sep 18 '16 at 22:02
1
$\begingroup$

Many useful pieces of software have "unbounded" loops that can't be trivially bounded. Any program with a user interface that waits for input, for example. You'd probably also be surprised by the number of software that contains an interpreter of some sorts: your browser, your PDF reader, the software on your printer...

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Thanks, but I'm aware of those and would count those examples as either trivial (waiting for input of any sort) or too closely related to theory or computation (interpreters). $\endgroup$ – Luka Mikec Sep 19 '16 at 12:03

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.