Decidable languages [duplicate]

Question

A recursive (decidable) language is defined as a language for which there exists an algorithm deciding if a string is or not in the language that terminates for every possible input.

The question is, does there exist a programming language/grammar/something that is able to represent all and only the algorithms that are a decider? I.e. all the possible programs that terminate, and not others?

Answer 1

Assume we have a programming language $L \subseteq \Sigma^* $ satisfying the following natural requirements:

1. Programs in $L$ always terminate. I.e., for every program $p\in L$, its semantics $[\![p]\!] : \mathbb{N}\rightarrow\mathbb{N}$ is a recursive total function.
2. There is an effective enumeration of $L = \{p_0, p_1, \ldots\}$. That is, given $i$ we can compute the program (a source code string) $p_i$. This essentially requires that the syntax is reasonably regular.
3. The language can be interpreted by a Turing machine. I.e., the function $r(i,n) = [\![p_i]\!](n)$ is (total) recursive.

The question then becomes: can $L$ express all the deciders? More formally, given any total $0,1$ valued recursive function $f$, can we always have $f = [\![p_i]\!]$ for some natural $i$?

Take the following function: $$ g(n) = \begin{cases} 0 & \mbox{if } r(n,n) \neq 0 \\ 1 & \mbox{otherwise} \end{cases} $$ We have that $g$ can be implemented by a Turing machine, since $r$ is total recursive. Since $g$ is total and returns in $\{0,1\}$ said machine is a decider.

Assume by contradiction $L$ can compute $g$, say $g = [\![p_i]\!]$ for some $i$. Then, by definition of $g$ and $r$ we have $$ [\![p_i]\!](n) = \begin{cases} 0 & \mbox{if } [\![p_n]\!](n) \neq 0 \\ 1 & \mbox{otherwise} \end{cases} $$ Now, what happens when $n$ is equal to $i$ ? $$ [\![p_i]\!](i) = \begin{cases} 0 & \mbox{if } [\![p_i]\!](i) \neq 0 \\ 1 & \mbox{otherwise} \end{cases} $$ So, $[\![p_i]\!](i)$ is zero iff it is nonzero -- contradiction.

We conclude that $g$ can not be implemented in $L$.