May 2001
This paper provides a review of the idealized model for mathematical calculations (Turing Machine) and our understating of neural level structures. The author also developed a Turing Machine emulator running on DEC's PDP11.
Introduction
Briefly, Alan Turing, a British mathematician and cryptographer invented (or more accurately) described the Turing machine in 1937 as a tool for studying the computability of mathematical functions and serve as an idealized model for mathematical calculations. This can be regarded as the first computer, albeit, on paper. Alan Turning called this device an “a(utomatic)-machine”
A Turing machine can be thought of as an abstract system with an infinite line of cells (known as a tape) that consists of adjacent cells. Each cell contains a written symbol. The symbols (including blanks) that are allowed on the tape are finite in number and characterised by their own character-set. These determine the symbols that are allowed to be written/read on the tape.
The tape head or the active element is positioned over a cell and reads a symbol from a cell and may write a new symbol onto a cell. The active element can move to an adjacent cell, either to the left or to the right carrying a property known as a "state". Change to this state is known as the "color" of the active cell underneath it.
The Machinery
The machinery of this theoretical device is a list of "transitions" that, given a current state and a symbol under the head, dictates what should be written on the tape, what state the machine should enter, and whether the head should move left or right.
The Theory
Although it is composed of basic capabilities, Turing argued that this machine can perform any computation. That is, it could realize anything that results from state-transition-based operations. Later, Turing conceptualized the mind itself as a result of operations at the neural level, thus progressing discussion in artificial intelligence studies.
Turing's hypothesis (also known as Church's thesis) is a widely held belief that a function is computable if and only if it can be computed by a Turing machine. This implies that Turing machines can solve any problem that a modern computer routine can solve. There are problems that can not be solved by a Turing machine (e.g., the Halting Problem and see NPCompleteness); thus, these problems can not be solved by a modern computer program. Turing proved in 1936 that a general algorithm to solve the Halting problem for all possible program-input pairs cannot exist. It is said that the halting problem is un-decidable over Turing machines.
Turing machines that are able to simulate other Turing machines are known as Universal Turing Machines. A more mathematical interpretation with similar "universal" properties was developed by Alonzo Church whose work on Lambda calculus intertwined with Turing's in computations known as the Church-Turing thesis supporting the idea that these machines provide a precise definition of an algorithm.
Turing's hypothesis and human-mind connection
One way to know that a simple mechanism has the same computational capabilities as a Turing machine is to see if it can emulate a Turing machine. Indirectly, it shows that humans are also Turing machines since we can emulate them.
No comments:
Post a Comment