ThesaHelp: references tz
Topic: what is a number
Topic: real numbers and floating point numbers
Topic: Turing machine
Topic: kinds of numbers
Topic: computer as state machine
Topic: nondeterministic processing
Topic: what is a computer
Topic: limitations of formalism
Topic: mathematics as a formal system
Topic: Godel's incompleteness theorem
 
Reference
Turing, A.M.,
"On computable numbers, with an application to the Entscheidungsproblem",
Proceedings of the London Mathematical Society, 2nd series , 42, pp. 230265. correction, 43:5446 1937, November 1936.
Google
Other Reference
reprinted in Davis, Martin, The undecidable, Raven Press 1965
Quotations
231 ;;Quote: the computable numbers are the real numbers whose decimal expression can be calculable by finite means; because human memory is limited
 231 ;;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
 231+;;Quote: the configuration of a Turing machine (i.e., state and read symbol) determines its possible behavior
 232 ;;Quote: a computing machine is an automatic machine that uses 0 and 1 for input and output
 232 ;;Quote: a choice machine is one with ambiguous configurations that are determined by an external operator; e.g., for an axiomatic system
 240 ;;Quote: the description number and standard description of a Turing machine encodes its state transition table in numbers and letters respectively
 241 ;;Quote: the computable sequences are enumerable because of the manyone relationship between Turing machine numbers and computable sequences
 241 ;;Quote: Turing defined a universal computing machine which when given the description number of M computes the same sequence as M
 246 ;;Quote: the sequence of computable numbers is not computable because of the halting problem; get an infinite loop when processing its own description number
Quote:
turiAM ;;249 "Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. ... [p. 250] The behavior of the computer at any moment is determined by the symbols which he is observing and his "state of mind" at that moment. We may suppose that there is a bound B to the number of symbols or squares which the computer can observe at one moment. If he wishes to observe more, he must use successive observations. We also suppose that the number of states of mind that must be taken into account is finite. The reasons for this are of the same character as those which restrict the number of symbols. In we admit an infinity of states of mind, some of them will be "arbitrarily close" and will be confused. ... Let us imagine the operations performed by the computer to be split up into "simple operations" which are so elementary that it is not easy to imagine them further divided. Every such operation consists of some change of the physical system consisting of the computer and his tape. ... [p. 252] The machines just described do not differ very essentially from computing machines as defined [above]
 252 ;;Quote: the Hilbert functional calculus can be modified so that an automatic machine will find all provable formulae
 252+;;Quote: construct a choice machine by successively computing the result for each possible sequence of choices
 259 ;;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

Related Topics
ThesaHelp: references tz (309 items)
Topic: what is a number (55 items)
Topic: real numbers and floating point numbers (37 items)
Topic: Turing machine (30 items)
Topic: kinds of numbers (24 items)
Topic: computer as state machine (20 items)
Topic: nondeterministic processing (19 items)
Topic: what is a computer (62 items)
Topic: limitations of formalism (93 items)
Topic: mathematics as a formal system (30 items)
Topic: Godel's incompleteness theorem (19 items)
