# Decidable languages [duplicate]

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?

• By diagonalization, no. ​ ​
– user12859
Commented Feb 11, 2016 at 20:36
• @RickyDemer Make an answer? Commented Feb 11, 2016 at 22:05

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