Sipser: Chapter 6

From CSWiki

Jump to: navigation, search

[edit]

Sections

Section 6.1
Section 6.2
Section 6.3
Section 6.4

[edit]

Selected solutions

Exercises 6.3 and 6.5 and Problems 6.9, 6.10, and 6.12 only, please!

Exercise 6.3

Show that if $A \leq_T B$ and $B \leq_T C$ then $A \leq_T C$ .

The statements $A \leq_T B$ and $B \leq_T C$ imply that there exists a machine that decides $A$ with an oracle for $B$ , $M_{A}^B$ and a machine that decides $B$ with an oracle for $C$ , $M_{B}^C$ . Then, assume a third machine exists called $M_{A}^C$ .
$M_{A}^C =$

Simulate $M_{A}^B$ .
If $M_{A}^B$ asks about an input $x$ in $B$ , simulate $M_{B}^C$ on input $x$ .

The existence of $M_{A}^C$ proves that $A \leq_T B$ .

Problem 6.12 is pretty cool.

Show that Th( $\mathcal{N}$ , <) is decidable.

Th( $\mathcal{N}$ , <) is reducible to Th( $\mathcal{N}$ , +). Any less than expression can be described using addition expressions because it means that for any numbers $i$ and $j$ , where $i < j$ , there exists a number $k$ that does not equal zero and can be added to $i$ to get $j$ . Using this knowledge, any expression in the form $i < j$ can be replaced with $\exists k[(i+k=j) \wedge (k+k \neq k)]$ . And because Th( $\mathcal{N}$ , +) is decidable, and
Th( $\mathcal{N}$ , <) $\leq_{m}$ Th( $\mathcal{N}$ , +), Th( $\mathcal{N}$ , <) is decidable.

[edit]

Sipser, Introduction to the Theory of Computation

Retrieved from "http://wiki.cs.grinnell.edu/mediawiki/index.php/Sipser:_Chapter_6"

Sipser: Chapter 6

From CSWiki

Sections

Selected solutions

Related Pages

Views

Personal tools

Navigation

Search

Toolbox