Марвин Мински задал мне следующий вопрос во время моего устного экзамена:
При прохождении ant он печатает двоичное число (например, 101) каждый раз, когда требуется шаг. Какова минимальная длина в цифрах, двоичное число может быть для него возможным указать, в каком направлении движется ant, не глядя на начало или конец строки? ant указывает вам двоичный номер.
Пример: двоичное число ant равно 101, и, следовательно, ant оставляет след, который выглядит следующим образом: 101101101101101101101. Обратите внимание, что нет способа определить, в каком направлении перемещается ant. Следовательно, это конкретное число не работает (но может быть трехзначное двоичное число, которое делает).
Пример: двоичное число ant равно 011, и, следовательно, ant оставляет след, который выглядит так: 011011011011011011. Опять же, нет способа узнать, в каком направлении перемещается ant, не глядя на концы строки.
Каков ответ на этот вопрос? Обратите внимание, что ответ не может быть просто примером двоичного числа, которое работает. Ответ должен включать доказательство того, что ни одно двоичное число длины меньше n-1 не будет работать, где n - это длина примерного двоичного числа, которое работает. Доказательство из исчерпывающего перечисления в порядке, но неприятное.:)
