nicht angemeldet
Moin,
dazu müsstest du eigentlich ein paar Semester theoretische Informatik belegen... ich versuch's trotzdem.
Ein halbes Semester reicht. Alternativ ein bisschen in Wikipedia stöbern: http://de.wikipedia.org/wiki/Turingmaschine.
Eine Turingmaschine ist eine (fiktive) Rechenmaschine, die durch Zustände und Zustandsübergänge definiert ist.
Ein Programm ist dann turingberechenbar, wenn die Turingmaschine dieses in polynomieller Zeit (zur Länge der Eingabe) berechnen kann.
Nein, eine Funktion ist turing-berechenbar, wenn (big surprise) es eine Turingmaschine gibt die diese Funktion berechnet. Mit der Zeit hat das erstmal gar nichts zu tun. Das was du meinst wären die Probleme die in Polynomialzeit lösbar sind, das ist erstmal uninteressant.
"A ist Turing-vollständig" heisst dann einfach nur dass A genauso mächtig ist wie eine universelle Turing-Maschine, man also in A eine universelle Turing-Maschine emulieren kann (und umgekehrt).
Da eine Turing-Maschine eine bestimmte Klasse von Berechnungsproblemen lösen kann (von der man annimmt dass sie alle Probleme umfasst die "intuitiv anschaulich berechenbar" sind), kann man dann auch mit A alle berechenbaren Probleme lösen.
Henryk Plötz
Grüße aus Berlin
~~~~~~~~ Un-CDs, nein danke! http://www.heise.de/ct/cd-register/ ~~~~~~~~
~~ Help Microsoft fight software piracy: Give Linux to a friend today! ~~