Here is a very cool add-on for Firefox.

https://addons.mozilla.org/en-US/firefox/addons/policy/0/966/33806?src=addondetail

This add-ons allow users to change the headers and values.

Have fun.

Skip to content
# Month: November 2009

## Firefox, Tamper Data

## Chomsky Hierarcy

## Learn you a Haskell for Great Good

## Theory of Computation, Recursively Enumerable Sets

## Theory of Computation, Complexity Theory

## The Church-Turing Thesis: Story and Recent Progress

## Theory of Computation, Turing Machine

## Theory of Computation, Definition of Information

## Towards a definition of an Algorithm

## Theory of Computation, Halting Problem

Here is a very cool add-on for Firefox.

https://addons.mozilla.org/en-US/firefox/addons/policy/0/966/33806?src=addondetail

This add-ons allow users to change the headers and values.

Have fun.

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 |

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.

Notes on Recursively Enumerable Sets

Here is some notes on Complexity Theory . There will be some other notes on Complexity Theory.

This is a very interesting talk. I liked it and recommend it.

Alan Turing, is a fascinating, genius man, who defines computation with Turing Machines. In this note, I tried to define Turing Machine.

Reference : Sipser’s book.

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.

Reference: Sipser’s Book.

http://www.sci.brooklyn.cuny.edu/~noson/algorithms.pdf

What is algorithm ?

Professor. Noson Yanofsky defines algorithm in his paper.

**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**.