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 **art** , **beauty 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.

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 where

*Q*is a finite, non-empty set of*states*- Γ is a finite, non-empty set of the
*tape alphabet/symbols* - is the
*blank symbol*(the only symbol allowed to occur on the tape infinitely often at any step during the computation) - is the set of
*input symbols* - is the
*initial state* - is the set of
*final*or*accepting states*. - 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):

- Q = {
**A**,**B**,**C**,**HALT**} - Γ = { 0, 1 }
- b = 0 = “blank”
- Σ = { 1 }
- δ = see state-table below
- q
_{0}=**A**= initial state - F = the one element set of final states {
**HALT**}

Variants of Turing Machine

- Single Tape Deterministic Turing Machine
- Multitape Deterministic Turing Machine
- 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.

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