Talk:Universal Turing machine

Original content?

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?

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)

Universal Turing Machine, So what?

So what?! I heard that so many times. Turing's ideas deal with one of the most unique, complex, and stubborn problems in philosophy, in our understanding of reasoning, the significance/reality of the universe in general.Problem is that our minds are tight to many assumptions that many people are not willing to study or question. I think the premise is that, there is no point in thinking about such things as "Straight Lines", "1+1=2" since "clearly" they "exist", and we cannot change them. If you think like that, stop reading.

Even more worrisome, people have stopped talking about such things. These things were at the front of conversations in ancient Greece, in tertulias during the middle ages, all but forgotten now, studied by only a few that roll their eyes.

And yet there is a problem with "Straight Lines." So, here is a jaded and futile effort to explain these problems and how Turing's ideas, 3,000 years later, are so relevant.

Let us review some starting assumptions:

1. Assumption: The world exists. It has laws of nature. We are born, learn the rules and use them for our benefit.
2. Assumption: The world is outside, complex, we will probably never know all the rules. For example, Einstein broke Newton's laws. Today, no scientist believes we have found all of the laws of motion, even with relativity.
3. Therefore, laws are not in our control, and we might not ever understand the complexity of nature. Therefore, a machine will never be able to process all algorithms possible for known and unknown behaviors of nature.

And yet the universal computer exists.

Quantum physicists, geologists, biologists, psychologists, heck, your grandma, are using the same computers. The same Turing-complete computers. So how could universal computers exist? Why don't they need a quantum extension, biology module, grand ma's recipe chip?

So there is something wrong with the above assumptions. The issue was discovered by a person called Socrates, and it was documented by his pupil Plato. Or at least that is the oldest, more impactful reference used in western thought. Socrates asked simple "stupid" questions. From that, he discovered that lines and points in space are not real, but also, they are not learned. Look at a baby deer, a baby elephant, as they run to their mom. Do you think they learned about straight lines in 30 minutes of living? More importantly, stop the silly assumption that we magically know things exist; the deer needs to see his mom. Do you think it learned to interpret complex 3d images from his eyes and do basic trigonometry to reach his mom in 30 minutes of living? No, the deer's mind was preprogrammed, so was yours.

The fact that our reasoning of existence can only happen with perception was clearly explained by Descartes. Add that to the list of books.

Regarding the fact that it is not possible for our mind to learn "everything" from experience, look at futile efforts from Hume, Berkely, Locke.

In sum, Idealists ask you something difficult, forget about physical existence. For your mind, things exist after you perceive and/or think/reason about them. Yea, then you believe they exist outside of you, but the issue remains: You are making that up after reasoning. So please understand that idealists are not saying that the physical world does not exist; they just say that it makes no difference in your mind; you need perception and reasoning first.

One more thing.

So how much of our reasoning is hardcoded? What is the difference between parallel lines in my mind and "reality"? Can we ignore this framework and make another "artificially" say where "1+1=3"? Why do we need this framework? Is it just for survival, Darwinian purposes? Some people have studied the mind's framework—people like Kant, Schopenhauer. Add Schopenhauer to the list of books; those are of the most fascinating and easy reads you will have in your lifetime, but do not attempt to read Kant until you finish a degree on old German letters.

Again for a silly, simple summary. Kant discovered the "obvious"? Without a preconceived perception processing framework, our mind could not process perception, or at least that is the way it works for a human being. In other words, our eyes work like a computer screen. Eyes have cells called cones and rods that send images to the brain as a collection of color pixels. There is no difference between random pixels and an image from the outside world without processing logic. These are just pixels, but our mind interprets the collection of pixels to find circles, lines, objects, movement, and from there, events in time, with causes and effects.

Your mind makes the world out of perception. Is that the "real world"? Of course not, we miss so many things. Infrared light, High pitch vibrations, and those are the things we know we are missing... could perceptions be interpreted in another way? Would an Alien "see" circles where the ratio of the circumference to the diameter is 3.14 ...?

Kant discovered that our framework has 4 essential parts, in my personal interpretation or foolish simplification:

1. Space - Where things exist
2. Time - Where things change
3. Arithmetic - How we quantify/ analyze things
4. Trigonometry - How we see things move

So add Kant commentators to your list of books. But do not waste your time reading the Critique of Pure Reason directly. By the way, "Critique of Pure Reason" means "Study of preconceived reasoning", don't look like an idiot saying that Kant criticized something. Unfortunately, he uses a difficult language, and no one pretends to understand it enough to translate it to modern language.

So what does all that have to do with Turing and his machine?

Remember that in Turing's times, there were no computers, but people imagined complex machines that could do logic or at least complex math. If you did not know about what I just said, the most logical thing was to think that you would need special machines for different natural problems; a machine to crack the atom, another to process sociology data, another for a flight autopilot, and another to write documents. At that time, Turing wondered, could there be a universal computing machine? He answered the question with the Turing machine. His Turing machine is not a mechanical prototype. It is a mind experiment. It isolates and solves a significant philosophical problem decisively.

A Turing machine is a machine similar to a teleprinter with a long piece of paper with symbols—any symbol. The device reads a sequence and then prints another. So Turing asked, can there ever be a machine that processes some input in a way that no machine could compute the output? No, he wrote:

"It is possible to invent a single machine which can be used to compute any computable sequence. If this machine U is supplied with the tape on the beginning of which is written the string of quintuples separated by semicolons of some computing machine M, then U will compute the same sequence as M."

This was astonishing. Hopefully, you see the implications to the ideas of free will, the architecture of the mind, the constraints to your perception of the world, the idea of a soul apart from the human body/brain. etc.

But why? Because as a Mathematician, he knew that our mind is not infinite; it does not learn to reason by observing endless nature, as Socrates discovered. Our mind reasons based on specific rules of logic, these rules are built-in in our brains, as Kant detailed, and a machine can follow these rules, which Turing discovered. In other words, if the machine cannot compute, then a human could not understand it either. Turing figured it out mentally. Today we all carry smartphones that carry Turing Complete processing units, and they can run any program imaginable by human logic. A computer can execute every sequence of logic that you can think of and return the result that any human will expect to see because humans are not free to decide how to reason. Turing was the first human being to know they were possible for sure and one of the first to try to build one.

Indeed, one of the greatest minds in the world and Turing machines of the most outstanding ideas in the world.

"The idea behind digital computers may be explained by saying that these machines are intended to carry out any operations which could be done by a human computer. " (Turing, 1950, "Computing Machinery and Intelligence")

"A man provided with paper, pencil, and rubber, and subject to strict discipline, is in effect a universal machine." (Turing 1948: "Intelligent Machinery", National Physical Laboratory Report)

"Turing's 'Machines'. These machines are humans who calculate. "(Wittgenstein, 1947, Remarks on the Philosophy of Psychology, Vol 1 )

--AlexDeGalicia (talk) 05:03, 17 February 2022 (UTC)

Alternating Turing machine

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

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?

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

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?)

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?

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

"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)