Church-Turing Thesis

I was completely fascinated by Godel’s Incompleteness theorem.

The theorem say’s that

Not all true statements are provable.

Though simplistically I can say that in a short sentence as previously mentioned, that statement ruined the life of so many mathematicians back then.  Mathematicians are known to devote their lives in a problem that seems to have no application in daily life but   only  for the sake of artbeauty and truth. As I quote one of the books I’ved read “Uncle Petros and the Goldbach’s Conjecture” by Apostolos Doxiadis(this book is one of my favorites, it depicts a mathematical obsession for the search of truth and beauty),

Mathematicians are born and not developed.

It’s  a destiny to be a Mathematician, one must be born with the gift of intellectual capability to be able to contribute a fraction of the Mathematical foundations.

Godel’s proof was so beautiful that, I myself cannot perceive it’s beauty. I must admit I am  not one of those geniuses who are meant to unravel that  life’s one of the greatest mystery.

Father of Computation

The great Alan Turing

When I entered Computer Science, I appreciate and love what Mr. Alan Turing proved in the  1920’s, Instead of explaining it the Godel way, He  introduced the concept of Computation, and proved that not all problems are solvable.

The commonly known as the first mathematical model of a computer is the Turing Machine, unlike Finite State machine and Push down automata, a Turing Machine can do whatever a present computer can do, and both are restricted to the limit of computation.

This Turing Machine is  a finite automaton with an access to an infinite tape, that serves as its memory. Initially the tape contains the input string and is blank everywhere else. The machine can read and write on the string and can move on either sides. The machine continues to move depending on the control sequences given by the finite state machine of the Turing machine. It either accepts or reject the input if it decides on the input.

Formal Definition of a Turing Machine

Hopcroft and Ullman (1979, p. 148) formally define a (one-tape) Turing machine as a 7-tuple M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle where

  • Q is a finite, non-empty set of states
  • Γ is a finite, non-empty set of the tape alphabet/symbols
  • b \in \Gamma is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
  • \Sigma\subseteq\Gamma\setminus\{b\} is the set of input symbols
  • q_0 \in Q is the initial state
  • F \subseteq Q is the set of final or accepting states.
  • \delta: Q \setminus F \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows “no shift”, say N, as a third element of the latter set.)

Anything that operates according to these specifications is a Turing machine.

The 7-tuple for the 3-state busy beaver looks like this (see more about this busy beaver at Turing machine examples):

Γ = { 0, 1 }
b = 0 = “blank”
Σ = { 1 }
δ = see state-table below
q0A = initial state
F = the one element set of final states {HALT}

Variants of Turing Machine

  1. Single Tape Deterministic Turing Machine
  2. Multitape Deterministic Turing Machine
  3. Nondeterministic Turing Machine

Though multitape or non deterministic Turing machine looks deceivingly powerful than the usual Turing Machine. They are proven to have the same expressive power. The three variants  differ on the resources needed.

One thought on “Church-Turing Thesis

  1. how are you!This was a really terrific website!
    I come from roma, I was luck to search your website in google
    Also I get a lot in your subject really thank your very much i will come every day

Leave a Reply

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

You are commenting using your 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