Talk:Universal Turing machine

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 

Original content?[edit]

This is clearly not original content. Can anyone track down the original so it can be attributed, or at least so the footnotes point somewhere? Joshf 03:28, 7 December 2006 (UTC) Try this link - link en.wikipedia.org/wiki/Talk:Turing_completeness - Also on that page someone asked about "Criterion for Turing-complete languages." Check Goldparser user group about message 950 "on our basic goal" for (an initial) description of Turing Completeness. Tokyo Joe

This article should probably be updated with this information: http://blog.wolfram.com/2007/10/the_prize_is_won_the_simplest.html —Preceding unsigned comment added by 199.46.200.232 (talk) 17:30, 24 October 2007 (UTC)


So What?[edit]

What is the significance of Turing completeness? The article doesn't tell. From a reader's perspective, a Universal Turing Machine looks like an insignificant little programming trick. Rogerfgay (talk) 10:13, 26 March 2008 (UTC)

I don't quite understand this question in the context of UTMs. But it is true that just because a machine looks like a UTM it may not be one. And if a machine is not Turing-equivalent it will not be capable of computing everything that is computable. (1) a UTM represents a TABLE of instructions that is "frozen" (unalterable) in hardware or firmware and which interprets the instructions and data (in a format pre-established by the machine's author) on the tape. But, (2) whether or not such a machine so constructed is Turing equivalent is another matter. All authors of such machines are responsible for demonstrating -- exhaustively -- that their proposed UTM's "instruction set" (defined by and executed via the TABLE) can indeed execute all the equivalent Turing instructions. About half of Turing's original proof was indeed a demonstration -- i.e. a constructive proof -- that the notion of a UTM was indeed possible. Bill Wvbailey (talk) 19:50, 26 March 2008 (UTC)
I revised the Mathematical section w.r.t. how Turing completeness was discussed, and I removed the following confused sentence: "If we define "universal Turing machine" (UTM) to include any Turing machine that simulates some Turing-complete computational model, not just Turing machines that directly simulate other Turing machines, a universal Turing machine can be fairly simple, using just a few states and a few symbols."
Firstly, the definition of UTM is not up for grabs; but more importantly, the sentence involves circular reasoning, because a "Turing-complete computational model" is essentially defined to be one that can simulate a UTM — it's a UTM that serves as a standard for comparison. Furthermore, a UTM *does* require only a few states and a few symbols.
--r.e.s. (talk) 04:06, 30 July 2008 (UTC)

Alternating Turing machine[edit]

Why no discussion, distinction, or reference, to the above? --Ludvikus (talk) 14:15, 29 September 2009 (UTC)

Dates of invention don't match those in Turning Test[edit]

Universal Turing Machine states "Alan Turing introduced this machine in 1936–1937."

Turing Test says "The test was proposed by Alan Turing in his 1950 paper Computing Machinery and Intelligence, which opens with the words: "I propose to consider the question, 'Can machines think?'"...

Did he invent the universal Turing machine before the Turning Test? Possible. I don't know - just asking...

Jwichman (talk) 10:22, 7 October 2010 (UTC)

He invented his machines (the basic machine and the Universal machine) in 1936, described them in his Master's thesis and professionally in a paper published in early 1937, and then published a follow-on (the Oracle machine) in 1939 in Princeton NJ for his PhD. He contributed to the Allies' WWII effort by cracking the German Enigma code-machines, and after the war contributed to one of the first true computers (I think it's the Manchester (U.K.) Mark I, or something like that). But after a scandal in the early 1950's he died by eating a poisoned apple. BillWvbailey (talk) 13:06, 7 October 2010 (UTC)

Definition?[edit]

Given that this is a mathematics article, I'm disappointed that it doesn't attempt to precisely define universal Turing machines, using instead only the vague term "simulation". I would have expected a definition that says that a TM U is universal iff there exists a total recursive TM Tr, taking a TM program P (appropriately encoded on tape), such that U(Tr(P)) halts iff P halts. In practice, one assumes something a little stronger: there must be a second total recursive function Tr', such that U(Tr(P,input)) halts iff P(input) halts, and Tr'(U(Tr(P,input))) = P(input) if P(input) halts. Note, however, that this requires a specific encoding of tapes with arbitrary alphabets. Erniecohen (talk) 13:35, 17 November 2010 (UTC)

I haven't seen this definition, but if you have a source (sources) go ahead and add something to the "Mathematical Theory" section. BillWvbailey (talk) 18:02, 17 November 2010 (UTC)

TM:s Were Not the "Origin" of Stored-Program Computer[edit]

Historians are quite unanimous that Eckert and Mauchly were not aware of Turing's paper when they built the ENIAC. Von Neumann definitely was (and he did advocate Turing's ideas elsewhere), but he only joined the ENIAC program at a late stage. Already before Von Neumann joined the project, Eckert and Mauchly had started to consider ways to read the ENIAC program from various media (Eckert's papers and memos show this). ENIAC was later converted to a stored-program computer.

It would be wrong to say that Turing's paper was the origin of the stored-program computer, as the fathers of that innovation most certainly didn't know about Turing's paper. In addition, Babbage's machines already introduced the stored-program concept several decades before Turing's paper (Eckert and Mauchly weren't aware of Babbage's ideas either). — Preceding unsigned comment added by 130.234.189.54 (talk) 07:27, 26 July 2013 (UTC)

Cryptic paragraph in Stored-program computer ( Was Von Neumann the hot shot programmer?)[edit]

A 3-sentance paragraph in the WP article Universal_Turing_machine#Stored-program_computer states:

As the Turing Machine was encouraging the construction of computers, the UTM was encouraging the development of the fledgling computer sciences. An early, if not the very first, assembler was proposed "by a young hot-shot programmer" for the EDVAC. Von Neumann's "first serious program ... [was] to simply sort data efficiently". Knuth observes ...

If the author (Davis) never discussed whether or not Von Neumann was that "hot-shot programmer", then perhaps the paragraph in WP should stand as it is written. But, if it known whether or not Von Neumann was the "hot shot", then the paragraph needs to be reworded. --guyvan52 (talk) 12:28, 4 August 2014 (UTC)

OK, when I re-read the paragraph as shown above, without the WP article's distracting in-line references (Daves yyyy:pp) then it is much more likely that Von Neumann was the "young hot shot". Nevertheless, the prose should be written. The rewrite should go like this:
An early, if not the very first, assembler was proposed by Van Neumann, "a young hot-shot programmer" for the EDVAC. Von Neumann's "first serious program ...
I can't make the edit because I am still not certain that Van Neumann was the "hot-shot", but if someone who read Davis' book affirms, then I volunteer to make the edit also fix the in-line references.--guyvan52 (talk) 12:44, 4 August 2014 (UTC)

Mention relation to meta-interpreters?[edit]

UTMs are related to meta-circular interpreters. Is this significant enough to mention in the article?

[I]t is worth noting that a Universal Turing Machine can be considered as simply a meta-interpreter incorporated within hardware. In this sense, meta-interpretation is one of, if not the most fundamental concept in Computer Science.([1], also to appear in the Machine Learning Journal in 2015)

pgr94 (talk) 16:16, 25 November 2014 (UTC)

machine computes[edit]

"Turing machine computes a certain fixed partial computable function". What does it mean, "machine computes"? "function from the input strings over its alphabet". The result of computation is a symbol on the tape? (The are many symbols on the tape. Which symbol is the value of function?)85.140.206.60 (talk) 10:15, 9 June 2015 (UTC)