A unary function f(x) is said to be partially n-computable if it is computed by some S program P such that P has no more than n instructions, every variable in P is among X,Y,Z1,...,Zn and every label in P is among A1,...,An,E.

Prove that for every n >= 0, there are only finitely many distinct partially n-computable unary functions.

This problem is in Chapter 2, Section 4 of Computability, Complexity, and Languages by M.Davis.

New contributor
dr.knowNothing is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 1
    $\begingroup$ This probably immediately follows from the fact that there are finitely many such programs $P$ and that any pair of distinct $n$-computable functions need to be computed by distinct programs. $\endgroup$ – Steven Nov 21 at 14:51
  • 1
    $\begingroup$ We're not looking for posts that are just the text of an exercise-style task. We're a question-and-answer site, so we require you to articulate a specific question about your situation - preferably one that will be useful to others who aren't looking at the exact same exercise. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Nov 21 at 19:30

Your Answer

dr.knowNothing is a new contributor. Be nice, and check out our Code of Conduct.

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

Browse other questions tagged or ask your own question.