[Home]TuringComplete

ec2-3-229-123-80.compute-1.amazonaws.com | ToothyWiki | RecentChanges | Login | Webcomic

See the [wikipedia article].



A TuringMachine? is a specific type of machine which has finite state but infinite memory.  The details can be described on its own page.

It has been shown multiple times every year in every ComputerScience? class on the planet that a TuringMachine? is powerful enough to perform any calculation within finite logic.
No it isn't. It's shown once in the course, and relied upon multiple times per lecture.
Once in the maths lectures, once in the CS lectures - possibly again in the dip lectures if you share any of those - and certainly by the tutor once and the students a couple of times.  --Vitenka
In the maths lectures? What maths lectures? It's certainly not in NatSci IA maths. By the tutor? My ComputationTheory? supervisor didn't consider it his job to relecture the entire course. By the students? Since when do they lecture?

This means that a TuringMachine? can emulate any other machine (of a certain finite class blah blah)

Thus any machine that can emulate a turing machine (which is quite easy to do, if you have infinite memory, which most theoretical machines do because it makes things far simpler) is also that powerful.  Which is quite useful really.  Such a machine (or language) is called TuringComplete.



CategoryComputing

ec2-3-229-123-80.compute-1.amazonaws.com | ToothyWiki | RecentChanges | Login | Webcomic
Edit this page | View other revisions | Recently used referrers
Last edited November 3, 2003 7:36 pm (viewing revision 2, which is the newest) (diff)
Search: