0
$\begingroup$

Please help me prove the following problem:

A unary function $f(x)$ is said to be partially $n$-computable if it is computed by some $\mathcal{S}$ program $\mathcal{P}$ such that $\mathcal{P}$ has no more than $n$ instructions, every variable in $\mathcal{P}$ is among $X, Y, Z_1, . . . , Z_n$ and every label in $\mathcal{P}$ is among $A_1,...,A_n,E$. Prove that if a unary function $f : N \rightarrow N$ is computed by a program with no more than $n$ instructions, then $f$ is partially $n$-computable.

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

I am quite confused by this problem because the statement at the beginning and the question that needs to be proved are just two ways of saying the same thing. The statement is "q if p" and the question is "if p then q" which both mean "p implies q". So I totally don't understand what is asked to be proved here.

$\endgroup$
1
  • $\begingroup$ Then prove that the ways (one talking about variables and labels, one about instructions, only) are saying the same thing. $\endgroup$ – greybeard Oct 3 '20 at 15:58
0
$\begingroup$

Well there are trivial two conditions you have to prove.

If $f:N\rightarrow N$ is computable in $n$ instructions, then there exists a corresponding program $P$ that computes it in $n$ instructions. $P$ could assign one new variable in every instruction, thus the program uses $\leq n$ new variables. Furthermore the program only contains $n$ instructions meaning there is one label for every instruction at max, hence the number of labels is $\leq n$. This completes the proof (that $f$ is partially n-computable)

$\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.