Theoretische Informatik - ganz praktisch

3Nichtdeterminismus: Ratende Automaten?

Die bisher behandelten Automatentypen haben alle eine gewisse Entsprechung in der realen Welt. Bei Turingmaschinen und entsprechend auch bei LBA versteht sich die Parallele von selbst, denn die Turingmaschine steht als universelles Berechnungsmodell stellvertretend für die üblichen Rechner aus unserem Alltag.

Umgekehrt ist allerdings genau genommen jeder einzelne reale Rechner nicht Turing-mächtig. Da er nur einen endlichen Speicher hat, gibt es zwar sehr viele, aber nur endlich viele Kombinationen von möglichen Speicherzuständen. Daher kann er, wie ein endlicher Automat, nur endlich viele verschiedene ...