Small two-state

From 2009.igem.org

(Difference between revisions)
Line 1: Line 1:
-
{|align="justify"
+
<html>
 +
<style type="text/css">
 +
#nav, #nav ul {
 +
position: relative;
 +
margin: 0 auto; /* purpose: allow centering ul table */
 +
padding: 0;
 +
display: table /* purpose: ul doesn't stretch width 100% */
 +
}
 +
#nav li {
 +
display: table-cell; /* purpose: li behaves like table-cell */
 +
position: relative; /* purpose: non-overlap li elements in ul */
 +
list-style: none; /* purpose: remove default html list-style */
 +
}
-
{| style="color:#1b2c8a;background-color:#0c6;" cellpadding="3" cellspacing="1" border="1" bordercolor="#fff" width="100%" align="center"
+
#nav li a {
-
!align="center"|[[Team:IBB_Pune|Home]]
+
display: block; /* purpose: non-overlap div on a */
-
!align="center"|[[Team:IBB_Pune/Team|The Team]]
+
margin: 0 1px 0 0; /* purpose: spacing main menu items */
-
!align="center"|[[Team:IBB_Pune/Project|The Project]]
+
padding: 4px 59px;
-
!align="center"|[[Team:IBB_Pune/Parts|Parts Submitted to the Registry]]
+
background-color: #336633;
-
!align="center"|[[Team:IBB_Pune/Modeling|Modeling]]
+
color: #FFF;
-
!align="center"|[[Team:IBB_Pune/Notebook|Notebook]]
+
text-align: right;
-
|}
+
text-decoration: none; /* purpose: remove underline from a */
 +
font: bold 13px arial;
 +
}
 +
#nav li a:hover {
 +
background-color: #00CC33;
 +
color: black;
 +
}
 +
 +
#nav div {
 +
position: absolute; /* purpose: li of div doesn't spread out */
 +
display: none;
 +
width: 10em;
 +
opacity: 0.8;
 +
filter: alpha(opacity=80);
 +
border: 1px solid #28B095;
 +
background: #EAEBD8;
 +
}
 +
 +
#nav span a, #nav div a {
 +
position: relative;
 +
display: block; /* purpose: a's in div have same width */
 +
margin: 0;
 +
padding: 5px 10px;
 +
text-align: left;
 +
font: 11px arial;
 +
}
 +
 +
#nav span a:hover, #nav div a:hover {
 +
background-color: #00CC33;
 +
color: #000;
 +
}
 +
 +
#nav span div {
 +
position: relative;
 +
margin: 0;
 +
border: none; /* purpose: reset border to none */
 +
border-top: 1px solid #5970B2; /* purpose: add a seperator */
 +
border-bottom: 1px solid #5970B2; /* purpose: add a seperator */
 +
opacity: 1.0; /* purpose: opacity already 0.8 by #nav div */
 +
filter: alpha(opacity=100); /* purpose: opacity already 80 by #nav div */
 +
}
 +
 +
#nav span div a {
 +
text-indent: 10px;
 +
}
 +
 +
#nav span div span div a {
 +
text-indent: 20px;
 +
}
 +
 +
#nav .expand {
 +
background-image: url('https://static.igem.org/mediawiki/2008/e/ef/Icon-expand.png');
 +
background-repeat: no-repeat;
 +
background-position: 95% 50%;
 +
}
 +
 +
#nav .collapse {
 +
background-image: url('https://static.igem.org/mediawiki/2008/c/cd/Icon-collapse.png');
 +
background-repeat: no-repeat;
 +
background-position: 95% 50%;
 +
}
 +
</style>
 +
 +
<script type="text/javascript" src="http://www.kuleuven.be/bioscenter/igem/js/jquery.js"></script>
 +
 +
<script type="text/javascript">
 +
function toggleElement(layer){
 +
var myLayer = document.getElementById(layer);
 +
if(myLayer.style.display=="none"){
 +
myLayer.style.display="block";
 +
myLayer.backgroundPosition="top";
 +
} else {
 +
myLayer.style.display="none";
 +
}
 +
}
 +
</script>
 +
 +
<script type="text/javascript">
 +
 +
function ddmsie() {
 +
$("#nav ul").css('display', 'inline-block');
 +
$("#nav li").css('display', 'inline');
 +
$("#nav a").css('display', 'inline-block');
 +
$("#nav a").hover(function () {$(this).css('background-color', '#252025')},
 +
function () {$(this).css('background-color', '#649cd7')});
 +
$("#nav div a").css('display', 'block');
 +
$("#nav div").css('left', '0');
 +
$("#nav div").css('top', '100%');
 +
$("#nav span div").css('top', '0');
 +
}
 +
 +
function ddmozilla() {
 +
 +
}
 +
 +
function ddnav() {
 +
$("#nav li").hover(
 +
function () {
 +
$(this).find("div:first").css('display', 'inline');},
 +
function () {
 +
$(this).find("div:first").css('display', 'none');}
 +
);
 +
 +
$("#nav span > a").toggle(
 +
function () {
 +
$(this).removeClass("#nav expand").addClass("#nav collapse");
 +
$(this).css('background-color', '#99AAFF');
 +
$(this).parent().find("div:first").css('display', 'block');},
 +
function () {
 +
$(this).removeClass("#nav collapse").addClass("#nav expand");
 +
$(this).hover(
 +
function () {
 +
$(this).css('background-color', '#d4e2ef');},
 +
function () {
 +
$(this).css('background-color', '#649cd7');}
 +
);
 +
$(this).parent().find("div:first").css('display', 'none');
 +
}
 +
).addClass("#nav expand");
 +
}
 +
 +
$(function () {
 +
if(jQuery.browser.msie) ddmsie();
 +
if(jQuery.browser.mozilla) ddmozilla();
 +
ddnav();
 +
});
 +
</script>
 +
<div align="center" id="nav">
 +
<ul>
 +
 +
<li><a href="https://2009.igem.org/Team:IBB_Pune">home</a></li>
 +
 +
<li><a href="https://2009.igem.org/Team:IBB_Pune/Team">team</a>
 +
<div>
 +
<a href="https://2009.igem.org/Team:IBB_Pune/Team">Meet the Team</a>
 +
<a href="https://2009.igem.org/Team:IBB_Pune/sponsors">Sponsors</a>
 +
</div>
 +
</li>
 +
 +
<li><a href="https://2009.igem.org/Team:IBB_Pune/Project">project</a>
 +
<div>
 +
<a href="https://2009.igem.org/Team:IBB_Pune/Project">Summary</a>
 +
<span><a>Details</a>
 +
<div>
 +
<a href="https://2009.igem.org/SNOWDRIFT">project1</a>
 +
<a href="https://2009.igem.org/Turing_machines"> project2</a>
 +
                <a href="https://2009.igem.org/Team:IBB_Pune/project/project3">project3</a>
 +
                <a href="https://2009.igem.org/Team:IBB_Pune/project/systems together">master plan</a>
 +
<a href="https://2009.igem.org/Team:IBB_Pune/project/Results">results</a>
 +
</div>
 +
</span>
 +
        <a href="https://2009.igem.org/Team:IBB_Pune/Modeling">Modeling</a>
 +
<span><a>Related</a>
 +
<div>
 +
<a href="https://2009.igem.org/Team:IBB_Pune/Applications">Applications</a>
 +
<a href="https://2009.igem.org/Team:IBB_Pune/history">history</a>
 +
<a href="https://2009.igem.org/Team:IBB_Pune/reference lit">Reading</a>
 +
</div>
 +
</span>
 +
</div>
 +
</li>
 +
 +
 +
<li><a href="https://2008.igem.org/Team:ESBS-Strasbourg/Project">misc</a>
 +
<div>
 +
<a href="https://2009.igem.org/Team:IBB_Pune/Links">Links</a>
 +
        <a href="https://2009.igem.org/Team:IBB_Pune/Protocols">Protocols</a>
 +
      </div>
 +
</li>
 +
 +
 +
<li><a href="https://2009.igem.org/Team:IBB_Pune/Parts">parts</a>
 +
<div>
 +
<a href="https://2009.igem.org/Team:IBB_Pune/Parts">Submitted Parts</a>
 +
<a href="#">Sandbox</a>
 +
</div>
 +
</li>
 +
 +
 +
<li><a href="https://2009.igem.org/Team:IBB_Pune/Notebook">notebook</a>
 +
 +
 +
</ul>
 +
</div>
 +
</html>
Turing machine.  
Turing machine.  

Revision as of 20:22, 10 July 2009

Turing machine.


Look at the following set of instructions.


Internal state of the machine tape state read by the machine output internal state output tape state output direction
A 0 A 0 Right
A 1 B 1 Right
B 0 A 1 Stop
B 1 B 1 Right


The leftmost column of the table shows us that this particular Turing machine has two internal states of the box which we have labeled as A and B to distinguish them. Now consider the third row of the set of instructions. This set of instructions is interpreted as follows--“If the machine is in state B and the machine reads the mark 0 on the tape, then the internal state changes to A, the mark on the tape is changed from 0 to 1 and the machine stops.” Similarly, the first row tells the machine-“If you are in state A and you read the mark 0 on the tape, you change your internal state to A, change the mark on the tape from 0 to 0 and move one step towards the right so as to read the next mark on the tape.”

Now consider the following tape:


0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0


Here we assume, that because the tape is infinite, there are infinitely many zeros to the right of this tape and an infinitely many zeros to the left of this tape. That is to say we have considered only a segment of the potentially infinite tape. The infinite tape would look something like this.


0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 - - - - - -


If this tape is fed to the Turing machine let us see what happens.

The Turing machine reads a zero on the tape [Note- initially the machine is in state A] which is somewhere to the left of our given sequence. According to the first instruction, it changes its internal state to A, changes the tape mark to 0, and moves one step towards the right. In essence there is no change in the tape but that the machine has moved forward one step along the tape. The machine will go on repeating this until it reads the first 1 on the tape. When this occurs, the machine will carry out the second set of instructions because the machine is in internal state A and it reads a 1 on the tape. It will subsequently change the 1 to 1 and change its internal state to B moving one step to the right. Then it encounters the second 1 on the tape which it changes to 1, changes its internal state to B and moves one step towards the right [in accordance with the fourth instruction] This will continue until the machine encounters the 0 which proceeds the sequence of six 1’s. This zero will be changed to 1 and the internal change will be changed to A and the machine will stop. After the action of this entire process the new tape will look like this:


0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0


Note that there is a sequence of seven 1’s as compared to the original six present initially on the earlier tape. So this Turing machine which I shall call UN+1 increases the sequence of 1’s by one unit, i.e. the new sequence consists of another consecutive 1 on the tape. The name UN+1 been given because if we consider the sequence of 1’s as the unary representation of any natural number, then UN+1 adds 1 to that number. {In the unary system 2 is represented as 11 while 4 is represented as 1111.}


Thus we have seen how the Turing machine performs a calculational procedure mechanically and deterministically.


Go Back

Retrieved from "http://2009.igem.org/Small_two-state"