0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ What are $A_n$ here? And what is $A$ used for? $\endgroup$
    – nir shahar
    Mar 7, 2022 at 20:48
  • $\begingroup$ @nirshahar A is a finite sequence of strings. I have updated the question with the definition of An above. $\endgroup$ Mar 7, 2022 at 20:53
  • $\begingroup$ 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? $\endgroup$
    – nir shahar
    Mar 7, 2022 at 21:12
  • $\begingroup$ @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. $\endgroup$ Mar 8, 2022 at 1:52
  • 1
    $\begingroup$ 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$... $\endgroup$
    – nir shahar
    Mar 8, 2022 at 10:08

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.