Behauptung
Das vertikale Baumumrundungsproblem ist nicht mit einem read-only-Kara-Programm lösbar.
unvollständige Beweisidee
|
Wir nehmen an, es gäbe ein solches Programm, das Kara für jede Höhe n der Baumreihe vom
Ausgangspunkt A zum Endpunkt E bringt. Auf dem Weg von A nach E muss Kara in Z ein erstes Mal
die Linie zwischen "links" und "rechts" betreten. Da es für jedes n ein Z gibt, muss Z
unendlich oft direkt über dem obersten Baum oder ohne Kontakt zum obersten Baum liegen. Mit
anderen Worten: Es können nicht beide Fälle endlich mal auftreten. Es gibt also unendlich viele
Lagen Z = Z(n), die in der "Sensorik" gleich sind. Da das Kara-Programm nur endlich viele
Zustände hat, muss es unendlich viele Lagen Z(n) mit paarweise verschiedenem n geben, die im
aktuellem Zustand und in der Sensorik identisch sind. Kara wird sich also in der Folge in
diesen Fällen identisch verhalten.(??? Wirklich? Die Umgebung ist eine andere! ???)
Damit kann Kara in diesen Fällen nur dann in E zum Stehen
kommen, wenn die Höhen gleich wären. Die unendlich vielen n, die zu den Höhen gehören, sind aber
alle verschieden, werden also sicher diese feste Höhe überschreiten. Dh. es gibt eine Baumreihe,
die höher als Z ist, das ist aber ein Widerspruch.
|
 |
