Изменения

Код Беккета-Грея был назван в честь ирландского писателя Сэмюэла Беккета, который интересовался симметрией. Его пьеса [http://en.wikipedia.org/wiki/Quad_(play) "Quad"] содержала в себе четырёх актёров и была разделена на 16 временных периодов. Каждый период заканчивался, когда один из четырёх актёров выходил на сцену или же, наоборот, появлялся на нейуходил с неё. Пьеса начиналась на пустой сцене, и Беккет хотел, чтобы каждое подмножество актёров появлялось ровно один раз. Ясно, что множество актёров, находящихся в данное время на сцене может быть представлено в виде 4-битного двоичного кода Грея. Беккет, однако, добавил дополнительное условие в сценарий: чтобы со сцены уходил всегда тот из актеров, кто находился на ней дольше остальных. Актёры могли быть представлены как [http://ru.wikipedia.org/wiki/FIFO FIFO очередь] так, что (из всех актёров на сцене) уходил всегда тот актёр, который был первым в этой очереди. Беккет не смог найти код Беккета-Грея для своей пьесы, да и вообще, исчерпывающее перечисление всех возможных последовательностей показывает, что такой код не существует для n = 4. Известно, что сегодня такие коды существуют для n = 2, 5, 6, 7, и 8, и не существуют для n = 3 или 4.