Turing machines

From 2009.igem.org

(Difference between revisions)
 
(19 intermediate revisions not shown)
Line 1: Line 1:
-
{|align="justify"
+
{{Team:IBB_Pune/header}}
 +
{{team:IBB_Pune/menu}}
 +
<html>
 +
<body bgcolor="blue">
 +
</html><br>
 +
<p><span style="font-weight:bold; font-size:200%; color:#0000cc;">Turing Machines</span></p><br>
-
 
+
<html>
-
{| style="color:#1b2c8a;background-color:#0c6;" cellpadding="3" cellspacing="1" border="1" bordercolor="#fff" width="100%" align="center"
+
<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.
-
!align="center"|[[Team:IBB_Pune|Home]]
+
-
!align="center"|[[Team:IBB_Pune/Team|The Team]]
+
-
!align="center"|[[Team:IBB_Pune/Project|The Project]]
+
-
!align="center"|[[Team:IBB_Pune/Parts|Parts Submitted to the Registry]]
+
-
!align="center"|[[Team:IBB_Pune/Modeling|Modeling]]
+
-
!align="center"|[[Team:IBB_Pune/Notebook|Notebook]]
+
-
|}
+
-
 
+
-
+
-
+
-
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 28: 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 64: Line 36:
If you are wondering, "HOW??"
If you are wondering, "HOW??"
<html>
<html>
-
<p><a href="https://2009.igem.org/Team:IBB_Pune/Project"> 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
Line 77: Line 48:
4. "The Emperor's New Mind", 2nd Edition,  Roger Penrose, Martin Gardner (1999), Oxford University Press
4. "The Emperor's New Mind", 2nd Edition,  Roger Penrose, Martin Gardner (1999), Oxford University Press
-
 
-
<html>
 
-
<p><a href="https://2009.igem.org/Team:IBB_Pune/Project"> Go Back</a></p>
 
-
</html>
 

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"