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

- C1 is the start state
- Ci yields ci+1
- And Ck is an accept state

**Definition:**

A language A is

Turing recognizableif some Turing Machine recognizes it.(Also called Turing recognizable language)

**Definition:**

Decidersare turing machine that halt on all input

**Definition:**

A Decider that recognizes some language is also said to

decidethat language

**Definition:**

A language A is

Turing – decidableif 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.

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