Chomsky Hierarcy

Type Grammar Machine Application
3 Regular Grammar Finite Automaton, NFA, DFA Pattern Matching, Regular Expressions
2 Context Free Grammar Pushdown Automata, PDA (Uses Stack) Programming Languages
1 Context Sensitive Grammar Turing Machine with Bounded Tape Most Natural Languages
0 Recursively Enumerable Turing Machine with Infinite Tape

Learn you a Haskell for Great Good

Haskell is one of the cool functional language out there. The tricky bit of Haskell is, you need to think everything as Mathematical functions and you can write your Haskell functions just like you write your math functions.

There are several companies out there uses Haskell. Haskell is not the most efficient language but it gets the job done.

Another key point of Haskell is use of Recursion. There is no iteration and everything is being done via Recursion. In computability theory we have seen that everything can be computed using Recursion.

Definition : Partially computable functions are the functions that we can write program using basic operations , namely addition, subtraction and conditional branch. Partially computable functions are called Partially recursive functions. Functions that are partially recursive and total are called Recursive functions. i.e : these functions are total and we can write program for them.

Anyways, haskell is cool in many ways. It s precise and uses recursion heavily.

Here is a good resource to learn haskell.

Theory of Computation, Definition of Information

Since the early 20th Century, Computer Scientists, Mathematicians have been trying to define Computation, Algorithm, and Information. For example; there are several formal definitions to “What is Computation?”. For example : Church’s Lambda Calculus, Godels Recursion Theory, Alan Turing’s Turing Machines and so on. All these abstract machines are identical. They can be reduced to each other and their purpose is to define, What is computation ?

In this post, We are trying to do define information.

Definition of Information

Reference: Sipser’s Book.

Theory of Computation, Halting Problem

Church-Turing Thesis :

There is no algorithm that, given a program of P and an input of that program, can determine whether or not the given program will eventually halt on the given input.

Halt(x,y) Predicate can be proven by Proof by Contradiction. x is an input and y is the program number. At the end we come the a contradiction as follows :

Halt(y,y) = ~Halt(y,y) Which is contradiction.

Halting Problem on wiki.