Für

ein gegebenes

Für ein gegebenes ist die Platzkomplexität die größte Anzahl von unterschiedlichen Arbeitsfeldern, auf die eine Berechnung von auf einer Eingabe der Länge zugreift.

Für

ein gegebenes

Wir konstruieren aus einer Turingmaschine und einem Wort eine Turingmaschine , die auf das Band schreibt und dann am Wortanfang hält.

Wir konstruieren aus einer Turingmaschine und einem Wort eine Turingmaschine , die auf das Band schreibt und darauf dann wie arbeitet.

Wir konstruieren aus einer Turingmaschine eine Turingmaschine und ein Wort , wobei sich auf dem leeren Wort wie verhält und wir wählen.

Eine Turingmaschine ist selbst eine partielle Funktion.

Partielle Funktionen dienen als Eingaben für Turingmaschinen.

Die Turingmaschine muss nicht auf jeder Eingabe halten, weshalb die von ihr berechnete Funktion möglicherweise nur partiell ist.

Jede Turing-berechenbare Funktion ist effizient berechenbar.

Jede im intuitiven Sinne berechenbare Funktion ist auch Turing-berechenbar.

Es gibt im intuiviten Sinne berechenbare Funktion, die nicht Turing-berechenbar sind.

Berechnungsprobleme, die nur die Antworten „ja“ und „nein“ haben.

Ungelöste Probleme in der Informatik.

Berechnungsprobleme, die nur die Eingaben „ja“ und „nein“ haben.