Marvin Minsky hat mich gebeten, die folgenden Fragen während meiner mündlichen Prüfung:Kürzeste bitstring deren unendliche Wiederholung unterscheidet sich nach der Umkehrung
Wie eine Ameise geht es eine binäre Zahl druckt (zum Beispiel 101) jedes Mal, dauert es einen Schritt zurück. Was ist die minimale Länge, in Ziffern, kann die binäre Zahl sein, damit man sagen kann, in welche Richtung die Ameise reist, ohne auf den Anfang oder das Ende des Strings zu schauen? Die Ameise sagt dir die Binärzahl.
Beispiel: Die binäre Zahl der Ameise ist 101, und daher lässt die Ameise eine Spur, die wie folgt aussieht: 101101101101101101101. Beachten Sie, dass es keine Möglichkeit, die Art und Weise zu sagen, ist die Ameise fährt. Daher funktioniert diese bestimmte Zahl nicht (aber es kann eine dreistellige Binärzahl geben, die das tut).
Beispiel: Die Binärzahl der Ameise ist 011 und die Ameise hinterlässt eine Spur, die folgendermaßen aussieht: 011011011011011011. Auch hier gibt es keine Möglichkeit zu sagen, auf welche Weise die Ameise reist, ohne die Enden der Kette zu betrachten .
Was ist die Antwort auf diese Frage? Beachten Sie, dass die Antwort nicht nur ein Beispiel für eine funktionierende Binärzahl sein kann. Die Antwort muss einen Beweis enthalten, dass keine Binärzahl mit einer Länge von weniger als n-1 funktioniert, wobei n die Länge der Beispiel-Binärzahl ist, die funktioniert. Ein Beweis durch erschöpfende Aufzählung ist in Ordnung, aber unangenehm. :)
Sie fragen nach einem strengen mathematischen Beweis, oder einfach Namen fallenlassen? – gbn
Warum geht die erste Spur nicht "101101101101101"? –
Zum Schließen als "nicht programmierungsbezogen" geschlossen. Vielleicht möchten Sie ein mathematisches Forum für Fragen wie diese versuchen –