some of the tech specs of "chrome"
1. "isolated" tabs designed to prevent browser crashes -- "keeping each tab in an isolated 'sandbox', Chrome is able to prevent one tab from crashing another and provide improved protection from rogue sites i.e. when a tab is closed in Chrome it frees the memory of the system".
2. more powerful JavaScript engine -- "Gogole team has also built a more powerful JavaScript engine, V8, to power the next generation of web applications that aren't even possible in today's browsers"
3. They have also used componenets from Apple's Webkit and Mozilla's Firefox
I havent got a chance to use this browser...if anyone do got that please blog in...
Monday, September 8, 2008
Saturday, July 5, 2008
QUOTE OF THE DAY
"The noblest thing a human being can experience is acceptance of the mystery."
What's the world's greatest lie? It's this: that at a certain point in our lives, we lose control of what's happening to us, and our lives become controlled by fate.
What's the world's greatest lie? It's this: that at a certain point in our lives, we lose control of what's happening to us, and our lives become controlled by fate.
Tuesday, April 22, 2008
Busy Beaver function realised using Turing MAchine
Consider a Turing machine with the binary alphabet {0, 1} and n operational states (often labelled 1, 2, ... n or A, B, C, ...) and an additional Halt state.
His definition of a Turing machine was as follows:
* The machine runs on a 2-way infinite (or unbounded) tape.
* At each step, two conditions --
1. the machine's current "state" (instruction); and
2. the tape symbol the machine's head is scanning
-- define each of the following:
1. a unique symbol to write (the machine can overwrite a 1 on a 0, a 0 on a 1, a 1 on a 1, and a 0 on a 0);
2. a direction to move (Left or Right but "none" is not allowed in this model); and
3. a state to transition into (may be the same as the one it was in).
* The machine halts if and when it reaches the special Halt state.
Now start with a blank tape (i.e. every cell has a 0 in it) and a TABLE of n instructions. Run the machine; if it halts, note the number of 1s it leaves on the tape.
The n-state busy beaver (BB-n) game is a competition to find an n-state Turing machine which leaves the largest number of 1s on its tape before halting.
In order to take part in this competition you must submit the description of an n-state Turing machine that halts along with the number of steps it takes to halt to a qualified umpire who must test its validity. It is important that you provide the number of steps taken to halt, because if you do not and your Turing machine does not halt, there is no general algorithm that the umpire can use to prove that it will not halt. Whereas if you do provide a finite number of steps along with a candidate machine, the umpire can (given enough time) decide whether or not the machine will halt in so many steps.
The busy beaver function Σ(n)
The busy beaver function Σ(n) is defined as the number of 1s that the champion Turing machine prints given the number n of "states" (Turing-instructions) and a blank tape at the outset.
Radó went on to demonstrate that there is a well-defined champion to the n-state busy beaver Game:
There are a finite number of Turing machines with n states and 2 symbols, specifically there are [4n+2]2n of them. In addition it is trivial that some of these are halting machines; i.e., there exists at least one n-state, 2-symbol TM that will halt, for every n.
Now define:
* En to be the finite, non-empty set of halting n-state, 2-symbol Turing machines.
* σ(M) = the number of 1s left on the tape after the Turing machine M is run on a blank tape for any M in En.
* Σ(n) = max { σ(M) | M in En} (The largest number of 1s written by any n-state 2-symbol Turing machine)
Since σ(M) is a non-negative finite number for any M halting (in En), and since En is a non-empty finite set, Σ(n) is a well-defined non-negative finite number for any n.
This Σ is the busy beaver function and any n-state, 2-symbol machine M for which σ(M) = Σ(n) (i.e. which attains the maximum) is called a busy beaver.
His definition of a Turing machine was as follows:
* The machine runs on a 2-way infinite (or unbounded) tape.
* At each step, two conditions --
1. the machine's current "state" (instruction); and
2. the tape symbol the machine's head is scanning
-- define each of the following:
1. a unique symbol to write (the machine can overwrite a 1 on a 0, a 0 on a 1, a 1 on a 1, and a 0 on a 0);
2. a direction to move (Left or Right but "none" is not allowed in this model); and
3. a state to transition into (may be the same as the one it was in).
* The machine halts if and when it reaches the special Halt state.
Now start with a blank tape (i.e. every cell has a 0 in it) and a TABLE of n instructions. Run the machine; if it halts, note the number of 1s it leaves on the tape.
The n-state busy beaver (BB-n) game is a competition to find an n-state Turing machine which leaves the largest number of 1s on its tape before halting.
In order to take part in this competition you must submit the description of an n-state Turing machine that halts along with the number of steps it takes to halt to a qualified umpire who must test its validity. It is important that you provide the number of steps taken to halt, because if you do not and your Turing machine does not halt, there is no general algorithm that the umpire can use to prove that it will not halt. Whereas if you do provide a finite number of steps along with a candidate machine, the umpire can (given enough time) decide whether or not the machine will halt in so many steps.
The busy beaver function Σ(n)
The busy beaver function Σ(n) is defined as the number of 1s that the champion Turing machine prints given the number n of "states" (Turing-instructions) and a blank tape at the outset.
Radó went on to demonstrate that there is a well-defined champion to the n-state busy beaver Game:
There are a finite number of Turing machines with n states and 2 symbols, specifically there are [4n+2]2n of them. In addition it is trivial that some of these are halting machines; i.e., there exists at least one n-state, 2-symbol TM that will halt, for every n.
Now define:
* En to be the finite, non-empty set of halting n-state, 2-symbol Turing machines.
* σ(M) = the number of 1s left on the tape after the Turing machine M is run on a blank tape for any M in En.
* Σ(n) = max { σ(M) | M in En} (The largest number of 1s written by any n-state 2-symbol Turing machine)
Since σ(M) is a non-negative finite number for any M halting (in En), and since En is a non-empty finite set, Σ(n) is a well-defined non-negative finite number for any n.
This Σ is the busy beaver function and any n-state, 2-symbol machine M for which σ(M) = Σ(n) (i.e. which attains the maximum) is called a busy beaver.
Subscribe to:
Posts (Atom)