QuoteRef: turiAM11_1936

topics > all references > ThesaHelp: references t-z

references t-z
what is a number
real numbers and floating point numbers
Turing machine
kinds of numbers
computer as state machine
non-deterministic processing
what is a computer
limitations of formalism
mathematics as a formal system
Godel's incompleteness theorem


Turing, A.M., "On computable numbers, with an application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 2nd series , 42, pp. 230-265. correction, 43:544-6 1937, November 1936. Google

Other Reference

reprinted in Davis, Martin, The undecidable, Raven Press 1965

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 many-one 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
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 up

ThesaHelp: references t-z (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: non-deterministic 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)

Collected barberCB 3/94
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.