Talk:Universal Turing machine

From Wikipedia, the free encyclopedia

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)

[edit] So What?

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)