Tu­ring­ma­schi­nen (nicht im BP)

Tu­ring­ma­schi­nen kom­men im Bil­dungs­plan nicht vor. Weil sie aber von sehr hohem theore­ti­schem In­ter­es­se sind, wer­den sie hier der Voll­stän­dig­keit hal­ber er­wähnt.

Eine Tu­ring­ma­schi­ne hat kei­nen Stack, son­dern ein Spei­cher­band, auf dem sie ihre Ein­ga­be vor­fin­det und auch ihre Aus­ga­be hin­ter­lässt. Im Un­ter­schied zum Stack (der ja immer nur Zu­grif­fe auf be­nach­bar­te Ein­trä­ge er­laubt) kann sie mit dem Schreib-/Le­se­kopf auf dem Band be­lie­big hin und her na­vi­gie­ren und auch wei­ter ent­fernt ste­hen­de Ein­trä­ge an­fah­ren, aus­le­sen oder neu schrei­ben. Au­ßer­dem ist das Band nach bei­den Sei­ten hin un­be­grenzt.

Damit sind Tu­ring­ma­schi­nen mäch­ti­ger als Kel­ler­au­to­ma­ten. Sie kön­nen z.B. auch kontext­sensitive Spra­chen er­ken­nen und sogar Ad­di­tio­nen, Multiplika­tionen und an­de­re Algorith­men ausfüh­ren, wie man sich an ein­fa­chen Pro­ble­men über­legt. Man kann den Au­to­ma­ten, der die Tu­ring­ma­schi­ne steu­ert, etwa so auf­bau­en, dass er beim Start zwei Zei­chen­ket­ten auf dem Band vor­fin­det (eine der Länge 3, dann ein Trenn­zei­chen, dann eine der Länge vier als Re­prä­sen­ta­ti­on von „3+4“), den Schreib-/Le­se­kopf in ge­eig­ne­ter Weise auf dem Band hin- und her­fährt und dabei schritt­wei­se eine neuen Kette der Länge 7 er­stellt.

Von theo­re­ti­schem In­ter­es­se sind Tu­ring­ma­schi­nen vor allem des­halb, weil sie sogar alle Algo­rith­men aus­füh­ren kön­nen. Das ist etwas über­ra­schend, denn Tu­ring­ma­schi­nen sind kaum kom­ple­xer als Kel­ler­au­to­ma­ten. Den­noch mar­kie­ren sie unter den Au­to­ma­ten­mo­del­len auch schon das obere Ende an Mächtig­keit: Kein an­de­rer Au­to­ma­ten­typ kann etwas kön­nen, was eine Tu­ring­ma­schi­ne nicht kann! Diese Gren­ze gilt für alle heu­ti­gen und zu­künf­ti­gen Mehrkern­prozessoren, Quan­ten- oder an­de­re Com­pu­ter egal wel­cher Bau­art; sie be­trifft jeden denk­ba­ren Al­go­rith­mus in jeder nur vorstell­baren Pro­gram­mier­spra­che.¹⁹

Dass Tu­ring­ma­schi­nen gleich mäch­tig sind wie „voll­wer­ti­ge“ Pro­gram­mier­spra­chen auf moder­nen Com­pu­tern, macht sie für die In­for­ma­tik noch in­ter­es­san­ter: Ist näm­lich ein Pro­blem für Tu­ring­ma­schi­nen un­lös­bar, dann kann über­haupt kein Al­go­rith­mus die­ses Pro­blem lösen.

Ein sol­ches Pro­blem hat schon Tu­ring sel­ber ge­fun­den: Das „all­ge­mei­ne Hal­te­pro­blem für Turing­maschinen“ ist recht ein­fach zu for­mu­lie­ren und doch un­lös­bar: „Wenn man eine be­lie­bi­ge vor­ge­ge­be­ne Tu­ring­ma­schi­ne A mit der Ein­ga­be E star­tet – wird sie ir­gend­wann an­hal­ten, oder wird sie in eine End­los­schlei­fe ge­ra­ten?“ Wäre das Pro­blem al­go­rith­misch lös­bar, könn­te man eine Tu­ring­ma­schi­ne H bauen, die an­hand des Bau­plans von A er­mit­telt, ob A mit der Ein­ga­be E ir­gend­wann an­hal­ten wird oder nicht. Tu­ring be­weist²⁰ dann, dass es so einen Ana­ly­sa­tor H aber nicht geben kann – und damit ist das all­ge­mei­ne Hal­te­pro­blem prin­zi­pi­ell un­lös­bar, denn noch mäch­ti­ge­re Ma­schi­nen kann es ja nicht geben.

¹⁹ Bei In­ter­es­se an die­sem Thema kann eine Re­cher­che etwa an fol­gen­den Be­grif­fen an­set­zen: Tu­ring-voll­stän­dig als Kri­te­ri­um: „kann diese Pro­gram­mier­spra­che alles, was Tu­ring­ma­schi­nen kön­nen?“ und Church‘sche These: „alle Be­rech­nungs­kal­kü­le, Au­to­ma­ten­mo­del­le und Pro­gram­mier­spra­chen, die über­haupt eine ver­nünf­ti­ge Pro­gram­mie­rung er­lau­ben, sind damit schon genau so mäch­tig wie Tu­ring­ma­schi­nen“

²⁰ Eine hüb­sche Dar­stel­lung des Be­wei­ses ent­hält der Kurz­film „Proof That Com­pu­ters Can't Do Ever­y­thing (The Hal­ting Pro­blem)“, auf Youtube z.B.: https://​www.​youtube.​com/​watch?​v=92WHN-​pAFCs

Hin­ter­grund­in­for­ma­tio­nen: Her­un­ter­la­den [odt][669 KB]

Wei­ter zu Sprach­ty­pen und zu­ge­hö­ri­ge Gram­ma­ti­ken