Deconstructing the VMS : A positionless ledger (part 1)

[Jorge_Stolfi]

I'm completely lost. How is it possible to generate an infinitely long string without cycles?

By not repeating the same sequence ad infinitum. No problem.

You two seem to be talking about different things.

If the ledger can generate infinitely many strings, it must have a cycle.  That's because a set of infinitely many words must have arbitrarily long words.   If a finite state automaton with N states generates a word with N or more letters, it must go twice or more through some state.  That means the automaton has a cycle.  Then traversing that cycle M times generates a word that contains a substring that is repeated M times, for any M.

On the other hand, if the alphabet has N letters, it is possible to create a word with ~N^K letters that does not repeat any substring of K letters.  These words are called "De Bruijn sequences".   For example, with 10 letters one can create a text of a million letters that does not repeat any substring of 6 or more letters. 

All the best, --stolfi