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 ...
Get Theoretische Informatik - ganz praktisch now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
