# How does one prove that DEC does not parameterize DEC?

The $$n$$th slice of a set $$A \subseteq \Sigma^{*}$$ is defined as:

$$A_n = \{x \in \Sigma^{*}\mid\langle n,x\rangle \in A\}$$

The definition of parameterization is as follows - $$C$$ parameterizes $$D$$ (also called $$C$$ is universal for $$D$$) if,

$$\exists A \in C \quad\text{s.t}\quad D = \{A_n|n\in \mathbb{N}\}$$

However, I have no idea how to prove that the class of decidable languages (DEC) can parameterize DEC.

• What are $A_n$ here? And what is $A$ used for? Mar 7, 2022 at 20:48
• @nirshahar A is a finite sequence of strings. I have updated the question with the definition of An above. Mar 7, 2022 at 20:53
• Thanks. How is $\langle n,x \rangle$ defined here? Are we working with binary alphabet (i.e, $\Sigma=\{0,1\}$) and $n$ is interpreted as a binary number? Mar 7, 2022 at 21:12
• @nirshahar n is a natural number. So to determine if a string is in A_n, we stick the number n in front of it and check it is in A. Mar 8, 2022 at 1:52
• But some natural numbers may not even be a part of your alphabet! This would make a syntactically problematic question here. If $\Sigma=\{a,b\}$, then what is $5a$ here? It is not part of $\Sigma^*$, since $5\notin \Sigma$... Mar 8, 2022 at 10:08

Okay first you need to know that there exists a numbering $$\phi$$ for all the Turing-Machines that is $$\phi: \mathbb{N} \to TM$$ is a computable surjection. This is often called discription number. Now we define: $$A = \{\langle p,w \rangle | \text{ the TM } \phi(p) \text{ accepts } w\}$$ This language is decidable since $$\phi$$ is computable and using the Universal TM we can simulate $$\phi(p)$$ on $$w$$. Thus $$A \in DEC$$. But now $$\{A_n|\, n\in \mathbb{N}\} = DEC$$ because for every TM $$B$$ there exists a $$n\in \mathbb{N}$$ such that $$\phi(n)$$ is an encoding of $$B$$. Hence $$A_n$$ is the language decided by $$B$$.