Sipser Chapter 3: Church Turing Thesis Summary

Part 1: Turing Machines

A Turing Machine M accepts string w if w is an element of L(M),

(L(M) is the set of strings recognized by M)

and on input w M has a series of configurations C1, C2, … Ck such that

  1. C1 is the start state
  2. Ci yields ci+1
  3. And Ck is an accept state

Definition:

A language A is Turing recognizable if some Turing Machine recognizes it.

(Also called Turing recognizable language)

Definition:

Deciders are turing machine that halt on all input

Definition:

A Decider that recognizes some language is also said to decide that language

Definition:

A language A is Turing – decidable if some TM decides it. (recursive language)

And as a corollary,

Every decidable language is Turing recognizable.

But not all Turing recognizable are decidable


Example 1

A TM that decides on {0^(2^n)}

A TM that decides on {a^(i) b^(j)c^(k) where ixj=k}

Variants of Turing Machine

1. Multitape Turing Machine The same with Turing Machine  except that it has k infinite number of tapes. They just  differ on the transition function

Delta: Q x Lambda(k)-> Q x Lambda(k) x {L, R, S}(k)

Theorem:

Every multitape TM has an equivalent single tape Turing Machine

As a corollary:

A language is Turing recognizable iff a multitape TM recognizes it

2. Non deterministic Turing Machine – Instead of the Usual Transition function

Delta: Q x Lambda= P(Q x Lambda x {L,R})

Theorem:

Every Non deterministic Turing Machine has an equivalent  deterministic Turing Machine

As a corollary

A language is Turing recognizable iff a ndTM recognizes it.

3. Enumerator – A variant of TM that enumerates all languages it recognize.

Theorem:

A language is Turing recognizable if some enumerator enumerates it.

Advertisements

One thought on “Sipser Chapter 3: Church Turing Thesis Summary

  1. hi!This was a really excellent Topics!
    I come from roma, I was fortunate to approach your topic in wordpress
    Also I obtain much in your subject really thanks very much i will come again

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s