Recognisability

A language or decision problem is recognisable if there exists a Turing machine that correctly accepts and halts for every ‘correct’ input. For a language, this means it accepts every word in the language and for decision problems, it means it can verify a correct solution only.

Definition §

Recognisability (Language) ^def-language

Let $A$ be a language. Then:

$$\text{A is (Turing-)recognisable}⟺\exists \text{TM, M}\text{ such that }A=L(M)$$

• $M$ is a Turing Machine
• This means, for every string $w$, $M$ accepts $w$ if $w\in A$. If $w\notin A$, then $M$ can reject or run forever.
• If we wanted to ensure $M$ always halts, we need $A$ to be decidable.

#tosee can i make this definition?

Recognisability (Decision Problem) ^def-problem

Let $P(\vec{x})$ be a decision problem (of arity $n$) over an input set $X=\{{\vec{x}}_1,{\vec{x}}_2,\dots {\vec{x}}_m\}$

$$\text{P is recognisable}⟺\exists \text{TM, M}\text{ s.t. }L(M)=\{⟨{\vec{x}}_1,P({\vec{x}}_1)⟩,⟨{\vec{x}}_2,P({\vec{x}}_2)⟩,\dots ⟨{\vec{x}}_m,P({\vec{x}}_m)⟩\}$$

• $M$ is a Turing Machine
• This means $M$ can verify a correct solution, $\vec{x}$ for $P$ (i.e. one where $P(\vec{x})=\top$), but it cannot show a wrong solution does not work (that requires $P$ to be decidable)

Closure Properties §

$$\text{L and LC are recognisable}⟹\text{L is decidable}$$

Done by simulating $H_L$ and $H_{L^C}$ in parallel.