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