Turing machines

From 2009.igem.org

(Difference between revisions)
 
(16 intermediate revisions not shown)
Line 1: Line 1:
 +
{{Team:IBB_Pune/header}}
 +
{{team:IBB_Pune/menu}}
<html>
<html>
-
<style type="text/css">
+
<body bgcolor="blue">
-
#nav, #nav ul {
+
</html><br>
-
position: relative;
+
<p><span style="font-weight:bold; font-size:200%; color:#0000cc;">Turing Machines</span></p><br>
-
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 */
+
-
}
+
-
 
+
-
#nav li a {
+
-
display: block; /* purpose: non-overlap div on a */
+
-
margin: 0 1px 0 0; /* purpose: spacing main menu items */
+
-
padding: 4px 59px;
+
-
background-color: #336633;
+
-
color: #FFF;
+
-
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>
+
-
+
<html>
-
Turing machines form an extremely exciting part of mathematics, yes; they are a piece of mathematics(!) which are elegant, simple and powerful. They form the basis of computer programming. They help us understand the nature of algorithms and how the mind works.
+
<p><p>Turing machines form an extremely exciting part of mathematics, yes; they are a piece of mathematics(!) which are elegant, simple and powerful. They form the basis of computer programming. They help us understand the nature of algorithms and how the mind works.
   
   
Let us first try to see what a Turing machine actually is.
Let us first try to see what a Turing machine actually is.
-
The scientist and brilliant mathematician Alan Turing came up with this idea in an attempt to solve a problem in mathematics known as ''Entscheidungsproblem''. It translates to "a decision problem", and it was put forward by the German mathematician David Hilbert. Hilbert’s problem was- is there any general algorithmic procedure for resolving mathematical questions or whether in principle such a procedure might exist?.
+
The scientist and brilliant mathematician Alan Turing came up with this idea in an attempt to solve a problem in mathematics known as ''Entscheidungsproblem''. It translates to "a decision problem", and it was put forward by the German mathematician David Hilbert. Hilbert’s problem was- is there any general algorithmic procedure for resolving mathematical questions or whether in principle such a procedure might exist?.</p></p></body>
-
 
+
</html>
-
Turing’s concept:
+
<p><span style="font-weight:bold; font-size:150%; color:#FF6600;">Turing’s concept:</span></p> 
-
[[Image:Turing.jpg|center]]
+
 
 +
[[Image:Turing.jpg|center|thumbnail|500px]]
Line 224: Line 23:
It can move the tape towards the right or left, allowing it to ‘read’ further marks on the tape.
It can move the tape towards the right or left, allowing it to ‘read’ further marks on the tape.
-
{|  
+
[[Image:tape4.png|center|500px|thumbnail]]
-
|-
+
-
! 0
+
-
! 0
+
-
! 0
+
-
! 0
+
-
! 1
+
-
! 1
+
-
! 0
+
-
! 1
+
-
!  1
+
-
! 1
+
-
! 1
+
-
! 0
+
-
! 1
+
-
! 0
+
-
! 1
+
-
! 0
+
-
! 0
+
-
! 0
+
-
! 1
+
-
! 0
+
-
|-
 
-
|}
 
Line 260: Line 36:
If you are wondering, "HOW??"
If you are wondering, "HOW??"
<html>
<html>
-
<p><a href="https://2009.igem.org/Small_two-state"> Click here</a></p>
+
<p><a href="https://2009.igem.org/Small_two-state"> <span style="font-weight:bold; font-size:125%; color:#0000cc;">Click Here</span></a></p>
</html>
</html>
-
 
+
<p><span style="font-weight:bold; font-size:125%; color:#FF6600;">References</span></p>
-
REFERENCES
+
1. http://en.wikipedia.org/wiki/Turing_machine
1. http://en.wikipedia.org/wiki/Turing_machine

Latest revision as of 02:35, 22 October 2009





Turing Machines


Turing machines form an extremely exciting part of mathematics, yes; they are a piece of mathematics(!) which are elegant, simple and powerful. They form the basis of computer programming. They help us understand the nature of algorithms and how the mind works. Let us first try to see what a Turing machine actually is. The scientist and brilliant mathematician Alan Turing came up with this idea in an attempt to solve a problem in mathematics known as ''Entscheidungsproblem''. It translates to "a decision problem", and it was put forward by the German mathematician David Hilbert. Hilbert’s problem was- is there any general algorithmic procedure for resolving mathematical questions or whether in principle such a procedure might exist?.

Turing’s concept:


Turing.jpg


Turing’s machine consisted of a box capable of performing the following actions on a tape supplied to it: It can ‘read’ the marks on the tape, It can erase the marks on the tape or can change the marks on the existing tape, It can move the tape towards the right or left, allowing it to ‘read’ further marks on the tape.

Tape4.png


The above is a sample of such a ‘tape’ which is fed to the machine. For simplicity we label the tape in only two ways viz. 0 and 1.

Turing allowed more complex markings but (heck) that shouldn’t bother us here.

Coming back to the box, as we have seen that the box can move the tape, change its marks etc. but it should be noted that the machine does these operations in a non-random, deterministic way. That is, we can predict what the action of the Turing machine on the tape will be. The box has a set of finite internal states, but can work algorithmically on potentially infinite calculations using the tape.

If you are wondering, "HOW??"

Click Here

References

1. http://en.wikipedia.org/wiki/Turing_machine

2. http://plato.stanford.edu/entries/turing-machine/

3. http://mathworld.wolfram.com/TuringMachine.html

4. "The Emperor's New Mind", 2nd Edition, Roger Penrose, Martin Gardner (1999), Oxford University Press

Retrieved from "http://2009.igem.org/Turing_machines"