0
$\begingroup$

Let $\Sigma$ be an alphabet, and denote by $\mathrm{ind}(\varphi_M^{(k)})$ the index set (w.r.t some numbering) of the $k$-ary partial computable function $\varphi_M^{(k)} : (\Sigma^*)^k \rightarrow \Sigma^*$, which represents the $k$-ary proper function of the Turing machine $M$. Is it the case that $\mathrm{ind}(\varphi_M^{(k)}) \subseteq \mathrm{ind}(\varphi_M^{(k + 1)})$ for every $k \geq 1$? I think this is true simply because every $k$-ary input to $M$ is realizable as a $(k+1)$-ary input to $M$ but with one input word blank. However, to formally show the inclusion is evading me. I thought applying the $S^m_n$ theorem would be helpful, but I think that merely establishes the inclusion for some Turing machine (not necessarily $M$). Any help would be appreciated.

$\endgroup$

1 Answer 1

0
$\begingroup$

You can define a machine implementing the computable function $(\Sigma^*)^k \rightarrow (\Sigma^*)^{k+1}$ for adding the blank to the set of inputs, then compose the machine implementing this function with your machine taking $k+1$ inputs to produce the required machine with $k$ inputs.

The $S^m_n$ theorem can be used to construct the index for the composed machine.

I'm not sure if you mean whether same machine should be used to represent two functions with different arity? I think they would be different machines.

$\endgroup$
1
  • $\begingroup$ This is true. I think as stated the answer to my question is no, then, because the composed machine, and hence its index, is different from the original machine. $\endgroup$ Jan 9 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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