Talk:Turing machine

From Wikipedia, the free encyclopedia

WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: A-BB+ Class High Priority  Field: Foundations, logic, and set theory
One of the 500 most frequently viewed mathematics articles.
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
B rated as B-Class on the assessment scale
Top rated as Top-importance on the assessment scale

This is the talk page for discussing changes to the Turing machine article.

  • Please do not use it as a forum for general discussion about the article's subject.
  • Sign and date your posts using four tildes (~~~~).
  • Place new comments after existing ones (but within topic sections).
  • Separate topic sections with a ==Descriptive header==.

Contents

[edit] Archives

[edit] I don't like the picture

Hello, I don't like the picture on the front page (artistic representation of Turing machine). In my opinion, Turing machine is a very simple concept, and any picture of it should capture the simplicity. Although the current picture is nice, it has lot of irrelevant details, which make a bad impression that Turing machine is some complex device, while it is not. I liked [1] much more for this page, although not perfect either - it uses rather dull shades of grey as symbols, and doesn't capture the notion of internal state.

I agree; the "artistic" picture seems completely irrelevant. I'll remove it. --Brouhaha 21:07, 19 May 2007 (UTC)
From the history, I see that an earlier, more relevant image was replaced by User:Alain Vey on May 16, with an image he apparently created, and the edit summary "(fix)". The misleading edit summary seems to me to be an indication that Vey was not acting in good faith, but rather trying to surreptitiously promote his own artwork. --Brouhaha 21:15, 19 May 2007 (UTC)

(Once again) I would suggest that authors who feel the need to add their "artistic" rendition to the article (this is the third of three "artistic" versions that I know of -- two with colors, this last one the most extravagant), submit them on the Turing machine gallery sub-article page where they can all coexist happily. As for a "best image?" Of all the images I've seen the "Poor Mug in a Box" is the simplest and most vivid but fails (in the 1974 original) because (as the correspondent noted above) it fails to show "the mug" holding a list of instructions -- it failed to show both "the poor mug" and "the mug" holding the instructions (!):

"We are not concerned with the mechanics or the electronics of the matter. Perhaps the simplest way to picture the thing is quite crudely: Inside the box there is a man, who does all the reading and writing and erasing and moving. (The box has no bottom: the poor mug just walks along between the ties, pulling the box with him.) The man has a list of m instructions written down on a piece of paper. He is in state qi when he is carrying out instruction number i." (Boolos and Jeffrey, 1974).

But the image also fails because the Turing machine is a machine -- a mechanism acting as if it were a man doing very simple things -- but in fact it is not a man, whereas Emil Post's image is truly of a man working in a series of boxes:

"The worker is assumed to be capable of performing the following primitive acts:
"(a) Marking the [paper inside the] box he is in (assumed empty)
"(b) Erasing the mark in the box he is in (assumed marked),
"(c) Moving to the box on his right,
"(d) Moving to the box on his left,
"(e) Determining whether the box he is in, is or is not marked.
The set of directions... [etc. etc.] (Emil Post (1936))

As noted in the "gallery" sub-article, computational machinery of the Turing-machine sort became practical only with the invention of the electromechanical relay (probably coupled with something like Hollerith punch-cards to act as the "Table of Instructions" . . . both rather visually-boring objects. The artistic challenge is to render elegantly (i.e. simply, accurately, interestingly, engagingly) this visual concept of machine following a table of instructions to print and erase symbols on an unbounded-length of paper tape (or an equivalent). wvbaileyWvbailey 19:36, 20 May 2007 (UTC)


[edit] Disproof of Universal Computing

I've proposed reverting the most recent change by Ewakened, because it seems like original research by one person being declared as The Truth. That is, this Selim Akl says that's the case, so universal computing is declared a "myth." I may be misunderstanding, but that claim if true is a refutation of the basic point of the article! So, it's like someone finding evidence that water is actually dry, and the page on water suddenly including a section on "the myth of wetness." Can we show that Akl's opinion is mainstream, or a minority view worth being included for its influence (like Creationism)? Otherwise it should be toned down to present Akl among "alternative views" or something rather than outright refutation. -Kris Schnee 19:07, 29 May 2007 (UTC)

Akl uses nonstandard definitions, so his results don't actually reflect on what is ordinarily meant by "universal machine" . Removing the claims here was probably the right thing to do, since I can't see how to rephrase them to make them relevant (Akl's use of words like "computable function" are not at all the same). There is probably a place at WP where AKL's research would fit in, perhaps under "computable function" somewhere, but certainly not here. CMummert · talk 23:26, 29 May 2007 (UTC)
Maybe under Church-Turing thesis? This deals with the concept that no single logical system can completely and accurately prove all true statements. -Kris Schnee 23:43, 29 May 2007 (UTC)

[edit] More history here?

(Response to comment in maths rating.)

Hi, wvbailey here. Over the past year I've pruned this article into subarticles . . . Most of the history can be found at algorithm. The issues are organizational: (i) (potentially) too-long article, (ii) that the two histories -- algorithm, Turing machine -- are pretty much the same. Would you suggest we create a new subarticle? If so, title? I've debated doing this to the algorithm history section, but I have felt reluctant because (as you suggest) the "read" is better with the history embedded in the main article, and reviewers at algorithm wanted more history. wvbaileyWvbailey 14:45, 21 May 2007 (UTC)

I agree with you that the read is better with the history embedded in the main article, both here and at algorithm. I'm surprised you consider the histories to be pretty much the same. I suppose the history and motivation for Turing machines could be considered a part of the history of algorithms, but it is surely only a part, since it concerns the theory of computation (or Computability theory), rather than, for example, the development of algorithms, specific algorithms and applications of algorithms. I therefore wonder whether there is scope for shortening the part of the algorithm history dealing with the development of theory and models of computation, and expanding on these aspects here and in other theory of computation articles. Geometry guy 12:54, 9 June 2007 (UTC)
You have a good point. I'm sort of thinking out loud in the following: With respect to "theory of algorithm", I have little information after ~1950's. Turing died in the early fifties, Gödel was slowly disintegrating, Kleene finished his Introduction to Metamathematics, Martin Davis and Kleene expressed in a simpler form Turing's Halting Problem, thereafter much theoretical work moved toward "mechanical computers" and "computability theory" aka computer science. An interesting article -- Logic -- in Encyclopedia Britannica remarks that not too much work in Logic is going on in the US anymore because the real knotty problems are thought to have been "solved", and logicians have a hard time placing themselves in universities. Something like this may have happened w.r.t. "algorithm" (theory of, as opposed to tons of work on instances of such as "greedy algorithms"), and "Turing machine" too, especially after the evolution of the Turing machine into the more user-friendly, computer-like counter machine and register machine models in the 1950's and 1960's.
Markov's monograph is one post-WWII approach (see algorithm characterizations). And Knuth's three-volume set (he's working slowly on a fourth) is important because it was an attempt to codify common algorithms -- I've used his books myself. I corresponded with Gurevich (see algorithm characterizations), about a "text" or other reference having to do with "history of, and theory of, algorithm", and he said he did know of any. Apparently he and just a few others are working in this field (he's a theorist at Microsoft). He pointed me to his papers, which I dutifully read. In one I ran into Robin Gandy's "Theory of Mechanism" and this I hunted down and read (tough read), but this has more to do with limitations of Turing machines and computability theory and the Turing- and Church-theses. Why "algorithm" (theory of) and "Turing machine" are so mixed together is that (I believe) most theorists now consider the Turing machine (or a Turing-equivalent model such register- or counter-machine) as the sine qua non, the ultimate platform, on which (an instance of) "algorithm" is mounted (or must be mountable ultimately). However, some (e.g. Gurevich) believe that the combined machine+instructions is indeed "algorithm", the two cannot be separated. Knuth's specification of his MIX-computer pseudo-code, and his writing of his algorithms in his code, is a (tacit) admission of this. Also Stone (see algorithm characterizations). So in some minds "algorithm = Turing machine+instructions" and in others "algorithm = Turing machine instructions" (see Gödel's characterization) and in others "algorithm" = Turing-equivalent assembly-language and/or pseudo-code + instructions written in same." To confuse the issue, Gurevich mumbles something about "communication with an external world". And this leads into an interesting philosophic thread (ontology) -- someone added the philosopher Daniel Dennett's take on algorithm characterizations w.r.t. "evolution" (i.e. evolution as an algorithm !), and I have been mulling whether to add Searle's take too (the Chinese room question -- syntax versus meaning -- where is the "meaner" and what role does "the meaner" play in "algorithm" (theory of)).
I am seeing in the above a fork in the road -- "History of the "Theory of algorithm"" versus "History of (instances of) algorithms." Originally a lot of the history was at Halting Problem, I pruned it and amplified it for algorithm. Turing conceived of his "machine" (i.e. mechanical model of a man working in a mindless, machine-like manner) as a route to solve a problem posed by Hilbert (the Entscheidungsproblem). That certainly needs to be added here at Turing machine. Ditto for Emil Post's expression of the same. I'll reread the pertainent section of Turing's biography to get some guidance, also Dawson's chapter III Excursus in Logical Dilemmas: The Life and wrok of Kurt Godel. Hopefully you and other correspondents have more ideas and takes on this. wvbaileyWvbailey

[edit] A stab at history

moved to main article page: wvbaileyWvbailey 19:54, 23 June 2007 (UTC)

[edit] A stab at philosophic implications

-- work in progress -- wvbaileyWvbailey 19:45, 25 June 2007 (UTC)

> Philosophic issues around the Cantor diagonal method [??]

> Turing's paper that prescribes his Turing Test:

Turing, A.M. (1950) "Computing Machinery and Intelligence" Mind, 59, 433-460. At http://www.loebner.net/Prizef/TuringArticle.html

"Can machines think?" Turing asks. In §6 he discusses 9 objections, then in his §7 admits he has " no convincing arguments of a positive nature to support my views." He supposes that an introduction of randomness in a learning machine. His "Contrary Views on the Main Question":

  • (1) the Theological objection
  • (2) The "Heads in the Sand" Objection
  • (3) the Mathematical Objection
  • (4) The Argument from Consciousness
  • (5) Arguments from Various Disabilities
  • (6) Lady Lovelace's Objection
  • (7) Argument from Continuity in the Nervous System [i.e. it is not a discrete-state machine]
  • (8) The Argument from Informality of Behavior
  • (9) The Argument from Extrasensory Perception [apparently Turing believed that "the statistical evidence, at least for telepathy, is overwhelming"] —Preceding unsigned comment added by Wvbailey (talkcontribs) 02:10, 2 October 2007 (UTC)

> "Foundations issues": foundations as philosophy [??] What is "calculable", How to define "effectively calculable", "number" etc. -- analog analysis versus digital computation. Philosophic notion of "intuitive" as used by the authors:

"† We shall use the expression "computable function" to mean a function caculable by a machine, and we let "effectively calculable" refer to the intuitive idea without particular identification with any one of these definitions." (Turing (1939) footnote in U p. 160)

Sieg (2002) states in his Calculations by Man and Machine: Conceptual Analysis that

"My objective is to resolve central foundational problems in logic and cognitive science that require a deeper understanding of the nature of calculations. . . . The claim for logic is almost trivial and implies the claim for cognitive science; after all, the relevant logical notions have been used when stiving to create artificial intelligence or to model mental processes in humans.
"The foundation problems problems come to the fore in arguments for Church's or Turing's Thesis, asserting that an informal notion of effective calculability is captured fully by a particular precise mathematical concept." (p. 390)

Gandy in particular has a section 10.5 Philosophical Significance of Turing's Analysis with 3 major bullet points:

  • (1) Analysis of what was vague and intuitive "stated with complete precision" (p. 80 -- also Godel's quote has this "kind of miracle" that "the diagonal procedure does not lead outside the defined notion" (Gandy quoting Godel p. 80)
  • (2) "Turing's analysis can be seen as part of the general movement, already in evidence in the seventeenth centruy, towards a mechanistic -- or physicalistic -- account of human thought and behavior." (p. 80)
  • (3) In contrast with Wittgenstein's question "how it is that a rule has been followed correctly when different applications of it are made to different cases", "Turing's analysis shows how following such a rule consists in the iteration of one of a fixed number of behavior patterns: to follow a rule is to repeatedly carry out a recipe... it does show that the use of rules with potentially infinitely many cases of application is just a rhetorical deive, which does not really raise a new sort of problem."

> Strong AI, weak AI problem of mind and free will versus rote machine (determinism vs non-determinism) (Hodges pp. 289-293)

"Note the question of whether there exist finite non-mechanical procedures not equivalent to any algorithm, has nothing whatwoever to do with the adequacy of the definition of "formal system" and of "mechanical procedure" (Gödel (1964) U p. 72)

> non-deterministic TM (posed by Turing as a c-machine, but not carried further except a footnote on p. 138 that simply says that if the choices are binary 0 and 1 to just successively ("using a systematic search" is Gandy's phrase) visit all the possible choices). Also: o-machine of 1939 [??]. See commentary Gandy (1988) p. 78

> Turing's analysis of a human computer:

  • Symbols to appear on discrete locations in space: "Computing is normally done by writing certain symbols on paper . . . divided into squares like a child's arithmetic book. . . . the two-diemnsional character of paper is no essential of computation.
  • Linear symbols or strings: "I assume then that the computation is carried out on one-dimensional paper, i.e. on a tape divided into squares" (U p. 135)
  • Finite strings of B symbols: "I shall also suppose that the number of symbols which may be printed is finite. . . It is always possible to use sequences of symbols in the place of single symbols." U p. 135. (Turing allows a number B of symbols to be observed at once, p. 127 )
  • Short symbol strings i.e. "immediate recognisability": "the compound symbols, if they are too lengthy, cannot be observed at one glance [he gives an example here of two long strings of 9's]"p. 136
  • Finite states of mind: "If we admitted an infinity of states of mind, some of them will be "arbitrarily close" and will be confused.
  • Simple steps so elementary: "Let us imagine the operations performed by the computer to be split up into 'simple operations' which are so elementary that it is not easay to imagine them further devided. . . in a simple operation not more than one symbol is altered. . . the squares whose symbols are changed are always 'observed' squares . . . each of the new observed squares is within L squres of an immediately previously observed squares." (p. 136)
  • ?: "the squares can be found by some process of which my type of machine is capable." (p. 137)
  • Deterministic part I:"The operation actually performed is determined . . . by the state of mind of the computer and the observed symbols. In particular they determine the state of mind of the computer after the operation is carried out."
  • Deterministic II: the notion of "State formula": The notion of "State of mind" can be removed by a 'note of instructions' and appended to the symbols on the tape: ". . .he must leave a note of instructions (written in some standard form) explaining how the work is to be continued. . . . the note of instructions must enable him to carry out one step and write the next note. . . the state formula at any given staage is determined by the state formula before the last step was made, and we assume that . . . there is an axiom U which expresses the rules governing the behavior of the computer, in terms of the relation of the state formula at any stage to the state formula at the preceding stage."

Sieg (2002) reduces these [restrictions] to the following:

  • ("B) (Boundedness) There is a fixed bound on the number of configurations that a computor can immediately recognize
  • "(L) (Locality) A computor can change ony immediately recgonizable (sub-) configurations
  • "(D) (Determinacy) The immediately recognizable (sub-) configuration determines uniquely the next computation step (and id)" (p. 396)

> Gandy (1988)'s complaint: he believes that Turing based his model (philosophically, fundamentally, "intuitively") on the modelled-behavior of a human computer doing a calculation, rather than on the (logically-)possible behaviors of a computational machine in space-time.

"Turing's analysis makes no reference whatsoever to calculating machines. Turing machines as a result, as a codifcation, of his analysis of calculation by humans. 30 It is true that Turing ws fascinated by machines and mechanical devices . . . but he evidently did not think tht ideas derived from actual calculating machines were sufficiently relevant . . . it is by no means obvious that the limitations described in Section 10.2 [?? ] apply to mechanical devices; Turing does not claim this." ( p. 77)
  • Gandy wonders what "finite means" means -- what limits are placed on computation? (p. 78)

--- end philosophy ---

[edit] Models equivalent to the Turing machine model

The parenthetical remark

(Interestingly, this seemingly minor relaxation enables the Turing machine to perform such a wide variety of computations that it can serve as a model for the computational capabilities of all modern computer software.)

Um, yes? First, and the more minor nitpick, it's not the Turing machine that is being relaxed, but the push-down automaton. Second, does it actually add anything to what is already a common motif throughout the article (from the very first sentence, in fact)? —Preceding unsigned comment added by 60.234.168.92 (talk) 20:05, 17 October 2007 (UTC)

[edit] A paradoxical situation

To keep discussion together, I'll remove this duplicate section and point to the discussion on this exact topic at Talk:Algorithm#A_paradoxical_situation. — Carl (CBM · talk) 20:37, 19 March 2008 (UTC)

[edit] Turing machines and the human brain

I reverted a change that stated an equivalence between what Turing machines can do and what the human brain can do. The relationship between Turing machines and the mind is complex, with several viewpoints in the literature I believe. The text that was added implied it is an accepted fact that the brain and Turing machines are equivalent, which I cannot believe is correct. Also, while I don't mind the idea of a discussion somewhere about the relationship between Turing machines and the human mind, I don't think it really belongs here. Wherever it goes, it will need to be more carefully researched and referenced. — Carl (CBM · talk) 15:10, 22 April 2008 (UTC)

Yes, while it's clear that a human can simulate a Turing machine (putting aside mortality, etc) I imagine there are some strong opinions about whether human brains can be simulated by Turing machines. People who believe in strong AI like me would tend to say "yes" while those who don't would tend to say "no" or "only a Turing machine so large as to be impractical to construct". Still others would say "yes but it's a poor model that fails to capture the essential high-level structure of the human brain." Ideally this would all go in some article discussing the philosophy of the man/machine divide, and we could link to it from here. Dcoetzee 17:03, 22 April 2008 (UTC)
I agree with all of the above. The jury of philosphers of mind is very much still in the jury room, debating this (in particular: Dennett versus Searle). Bill Wvbailey (talk) 20:11, 22 April 2008 (UTC)