Map Index Random Help

## QuoteRef: turiAM11_1936

topics > all references > ThesaHelp: references t-z

ThesaHelp:
references t-z
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:
non-deterministic 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. 230-265. correction, 43:544-6 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 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 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 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