# Halting Problem

Halting Problem is closely related with reduction.

## Church-Turing Thesis

• Intuition of Algorithm equals Turing machine that halts on every input.
• solve equals decide
• decision problem equals language
Object O $\to$ "O"

Problem; Given $G$, is $G$ is a connected graph?
Language:

## Reduction

Abstract

A reduction from A(A over ${\mathrm{\Sigma }}_{A}$) to B(B over ${\mathrm{\Sigma }}_{B}$) is a recursive(computable) function $f\left({\mathrm{\Sigma }}_{A}^{\ast }\right)\to {\mathrm{\Sigma }}_{B}^{\ast }$ such that for $w\in {\mathrm{\Sigma }}_{A}^{\ast }$, $w\in A$ iff $f\left(w\right)\in B$

Theorem: Suppose there is a reduction f from A to B. If B is recursive, that A is recursive.

Proof: $\mathrm{\exists }{M}_{B}$ decides $B$, find ${M}_{A}$ to decide $A$.
${M}_{A}$ = on input $w$
(1) compute $f\left(w\right)$
(2) run ${M}_{B}$ on $f\left(w\right)$
(3) output the result

## Countable

What is Countable

A set is countable if it is finite or it is equinumerous with $\mathbb{N}$.
Let $A$ be a set. The following statements are equiv.
(1) A is countable
(2) $\mathrm{\exists }$ injection $f:A\to \mathbb{N}$
(3) there exists some way to enumerate $A$ such that for $a\in A$, $a$ can be enumerated within n steps where n only depends on $a$

Lemma: Any subset of a countable set is countable

Lemma: Turing Machine is countable.

Let $\mathrm{\Sigma }$ be an alphabet. ${\mathrm{\Sigma }}^{\ast }$ is countable

enumerate all the strings in ${\mathrm{\Sigma }}^{\ast }$, in increasing length $\mathrm{\forall }w\in {\mathrm{\Sigma }}^{\ast }$, $w$ will be listed within

$\mathbb{L}$ is uncountable

Let $\mathrm{\Sigma }$ be some alphabet
Let $\mathbb{L}$ be the set of all languages
Suppose that $\mathbb{L}$ is countable
The language in $\mathbb{L}$ can be listed as

${L}_{1},{L}_{2},{L}_{3},\dots$

Since ${\mathrm{\Sigma }}^{\ast }$ is countable, the strings in ${\mathrm{\Sigma }}^{\ast }$ can be listed as $$S_1, S_2, S_3, \dots$$
$D=\left\{{s}_{i}:{s}_{i}\notin {L}_{i}\right\}$ is a language over $\mathrm{\Sigma }$

## Definition

Give the definition of $H$ and ${H}_{d}$

• $H$ is recursively enumerable but not recursive.
• ${H}_{d}$ is not recurisively enumerable.
• If there is a reduction from $H$ to $A$, $A$ is not recursive

## Examples

• $A$ = {"$M$": $M$ is a TM that halts on empty input} is not recursive
• $B$ = {"$M$": $M$ is a TM that halts on some input} is not recursive
• $C$ = {"$M$": $M$ is a TM that halts on every input} is not recursive
• $D$ = {"${M}_{1}$""${M}_{2}$": ${M}_{1}$ and ${M}_{2}$ are two TMs with $L\left({M}_{1}\right)=L\left({M}_{2}\right)$} is not recursive
• ${R}_{TM}$ = {"$M$": $M$ is a TM with $L\left(M\right)$ is regular} is not recursive
• $C{F}_{TM}$ = {"$M$": $M$ is a TM with $L\left(M\right)$ is context-free} is not recursive
• $RE{C}_{TM}$ = {"$M$": $M$ is a TM with $L\left(M\right)$ is recursive} is not recursive
Rice's theorem

Rice's theorem
$R$ = {"M": $M$ is a TM with $L\left(M\right)\in \mathcal{L}$} is not recursive where $\mathcal{L}$ is a proper, non-empty subset of all recursively enumerable language.

Proof: Make a reduction from $H$ to $R$
(1) If $\varnothing \notin \mathcal{L}$
construct f("M""w") = on input $v$
step1 run $M$ on $w$
step2 run ${M}_{A}$ on $v$, where ${M}_{A}$ satisfy that $L\left({M}_{A}\right)\in \mathcal{L}$

if and only if
(2) If $\varnothing \in \mathcal{L}$
transform the the problem from $\mathcal{L}$ into $\overline{\mathcal{L}}$

## Closure Property

operator recursive recursive enumerable
$\cup$
$\cap$
$\stackrel{―}{}$ ×
$\circ$
$\star$
Lemma: A language $A$ is recursive if and only if $A$ and $\overline{A}$ are recursively enumerable

$H$ is recursively enumerable, $\overline{H}$ is not recursively enumerable

According to the Lemma, because $H$ is not enumerable

## Turing Enumerable

### Definition

We say a TM $M$ enumerates a language $L$ is for some state $q$,

$L=\left\{w:\left(s,▹\bigsqcup _{―}\right){⊢}_{M}^{\ast }\left(q,▹\bigsqcup _{―}w\right)\right\}$

## Lexicographically Turing Enumerable

### Definition

Let $M$ be a TM that enumerates $L$
We say M lexicographically enumerate $L$ if whenever

$\left(q,▹\bigsqcup _{―}w\right){⊢}_{M}^{+}\left(q,▹\bigsqcup _{―}{w}^{\prime }\right)$

${w}^{\prime }$ is after $w$ in lexicographically order, ${⊢}_{M}^{+}$ means at least one step.

What is lexicographical?

## Grammar

• Definition: A grammar is 4-tuple $G=\left(V,\mathrm{\Sigma },S,R\right)$
• $V$ is an alphabet
• $\mathrm{\Sigma }\subseteq V$: the set of terminals
• $S\in V-\mathrm{\Sigma }$: start symbol
• $R$: a finite subset of $\left({V}^{\ast }\left(V-\mathrm{\Sigma }\right){V}^{\ast }\right)×{V}^{\ast }$
• compared with Context Free Grammar, the Grammar is unrestricted grammar.
• ${A}_{G}$ = {"G""w": $G$ is a grammar that generates $w$} is not recursive