Group:
grammar
Group:
machine model
Topic:
computer as state machine
Topic:
formal methods and languages
Topic:
Godel's incompleteness theorem
Topic:
history of computers
Topic:
history of programming
Topic:
infinity and infinitesimal
Topic:
mathematics as a formal system
Topic:
Petri net
Topic:
pointer machines
Topic:
state
Topic:
Turing test
Topic:
von Neumann computer
Topic:
what is a computer
| |
Summary
Turing invented his widely used model of computability in 1936. He started with an assumption of finitude, that computation is performed with a finite set of states. Babbage had arrived at the same idea in the 19th century. Turing defined a computable number as a number with a finite representation. Then he defined a state machine for computing the computable numbers.
His construction was simple. A Turing machine has a finite set of states, a tape, a mechanism for reading, writing, and moving the tape, and a state transition table. A configuration consists of the current state, the tape's position, and the current symbol on the tape. The state transition table defines the next configuration.
It is fairly straightforward to encode a configuration and hence to encode a description of the machine. Then one can define a universal machine which given a description duplicates the behavior of the corresponding machine. It is this construction that gives the Turing machine its power. Furthermore, it reduces the computable numbers to the programs which compute them. These programs are in turn numbers, and so the computable numbers are enumerable. A diagonalization argument further proves that simple questions are undecidable, e.g., whether or not a program halts. This implies that the sequence of computable numbers is not computable.
Other formalizations of computability are equivalent to Turing machines. This leads to the widely held conjecture that computability is the same as computable by a Turing machine. Godel states that Turing machines is the model for formalism. (cbb 4/94)
Subtopic: computable numbers 
| Quote: the computable numbers are the real numbers whose decimal expression can be calculable by finite means; because human memory is limited [»turiAM11_1936]
| | Quote: a man computing a real number is like a machine with a finite set of states, a tape divided into squares, and a moveable reader/writer [»turiAM11_1936]
| | Quote: Babbage substituted unbounded time for unbounded space; allows a finite machine to make calculations of an unlimited extent [»babbC_1864, OK]
|
Subtopic: universal Turing machine
| Quote: with a universal Turing machine, you can program it for each different job [»turiAM9_1947]
| | Quote: Turing defined a universal computing machine which when given the description number of M computes the same sequence as M [»turiAM11_1936]
| | Quote: the description number and standard description of a Turing machine encodes its state transition table in numbers and letters respectively [»turiAM11_1936]
| | Quote: the configuration of a Turing machine (i.e., state and read symbol) determines its possible behavior
| | Quote: the computable sequences are enumerable because of the many-one relationship between Turing machine numbers and computable sequences [»turiAM11_1936]
| | Quote: compared notes about Turing's description of his universal machine; large individual differences in style and evaluations [»naurP4_1993]
| | Quote: Newman and Turing wanted to build a universal Turing machine
| | Note: first run of universal pointer machine [»cbb_2000, OK]
|
Subtopic: computability, halting
| Quote: the sequence of computable numbers is not computable because of the halting problem; get an infinite loop when processing its own description number [»turiAM11_1936]
| | Quote: there is no general process to determine whether a given formula is provable; contrast with Godel's proof that there exist propositions U such that neither U nor -U is provable [»turiAM11_1936]
| | Quote: the halting probability is a well-defined real number with no mathematical structure; the bits are random [»chaiGJ_2001]
|
Subtopic: Turing-Church thesis
| Quote: a constructive process is one that a machine can carry out [»copeBJ_1999]
| | Quote: Turing machines and neuron nets are equivalent, also Church's lambda-definability and Kleene's primitive recursiveness [»mccuWS_1943]
| | Quote: formal systems or formalisms are the same as Turing machines [»godeK_1931]
| | Quote: either the Turing-Church thesis implies that all physically realizable processes can be duplicated by computers or it does not limit physical processes [»conrM5_1985]
| | Quote: Church proposed lambda functions and recursive functions as equivalent definitions of effectively calculable. These widely different definitions support his thesis [»churA_1936]
| | Quote: Church's definitions of effective calculability include algorithms and a large class of provable theorems in a system of symbolic logic [»churA_1936]
| | Quote: Church proposed a definition for effectively calculable functions and demonstrated an unsolvable problem [»churA_1936]
|
Subtopic: examples
| Quote: make Zuse's Z3 a bounded Turing machine by gluing the ends together; simulate branching and indirect addressing with arithmetic [»rojaR3_1998]
| | Quote: announcement of Manchester "baby" computer; universal, fully electronic, 32 words of storage, adders, multipliers, control unit [»willFC9_1948]
| | Quote: Manchester "baby" computer is universal; negate x, subtract x, test sign of accumulator, goto, and stop [»willFC9_1948]
| | Quote: practical computing machines dial the position of information in a store; delay of a few microseconds; most are universal [»turiAM9_1947]
| | Quote: turn networks of NAND gates into components that, depending on initial conditions, invert signal, always 1, or alternate; training can create a universal Turing equivalent [»turiAM9_1947]
|
Subtopic: Turing machine and type
| Note: a type Turing machine selects transition table by type; allows decomposition [»cbb_1990, OK]
| | Note: need 6 instructions to implement a Turing machine's Next and Previous transitions [»cbb_1990, OK]
| | Note: type acts like a limited state of a Turing machine; defines offsets; same type if same label [»cbb_1990, OK]
|
Subtopic: problems with Turing machines
| Quote: the finite automaton is a better approximation to physical machines than are Turing machines; e.g., Kleene's regular events and McCulloch and Pitts nerve-nets [»rabiMO4_1959]
|
Related Topics
Group: grammar (8 topics, 181 quotes)
Group: machine model (13 topics, 206 quotes)
Topic: computer as state machine (20 items)
Topic: formal methods and languages (53 items)
Topic: Godel's incompleteness theorem (19 items)
Topic: history of computers (66 items)
Topic: history of programming (91 items)
Topic: infinity and infinitesimal (37 items)
Topic: mathematics as a formal system (30 items)
Topic: Petri net (44 items)
Topic: pointer machines (17 items)
Topic: state (35 items)
Topic: Turing test (13 items)
Topic: von Neumann computer (14 items)
Topic: what is a computer
(62 items)
|
