Church's thesis and the conceptual analysis of computability (Q2472612)

Denote a string of \({n}\) strokes by \({\underline{n}}\). Let the semantics \({d(\underline{n})=m}\) mean that \({n}\) strokes represent the number \({m}\). A Turing machine (TM) \({M}\) computes a string-theoretic function \(\varphi\) if \(\varphi ({\underline{n}})={\underline{m}}\) for some strings of strokes \({\underline{n}}\) and \({\underline{m}}\). TM \({M}\) computes a number-theoretic function \(f(n)=m\) relative to the semantics \(d\) just in case \({M}\) computes a string-theoretic function \(\varphi\) such that \(\varphi({\underline{n}})={\underline{m}}\) iff \({f(d(\underline{n}))}={f(d(\underline{m}))}\). A number-theoretic function \({f}\) is Turing-computable relative to the semantics \(d\) just in case some TM computes \({f}\) relative to \({d}\). The same TM computes different numerical functions relative to different correlations \({d}\) between strings and numbers. Church's thesis (the class of all algorithms coincides with the class of all partial recursive functions) is investigated with respect to different functions \({d}\) of representation of a natural number \({n}\) with the help of a string of \({m}\) strokes on the tape of a Turing machine.