You've prob heard of Turing Machines, but how abt the simplest model of computation, the automaton/finite state machine?

Automata can be pictured as a state diagram like the one below

Automata we use IRL only take finite inputs, but what if we allow infinite input strings? ()

The diagram models a printer that only prints a file if the binary code has an odd # of 1's.

It doesn't model the printer actually printing, just the computation to decide whether to print at all.

Circles are states the printer can be in, & double circle means an accept state.

Arrow btwn states A & B labeled w/ character x indicates transition A-->B if next character of input string is x

Arrow w/ no label points to start state (where to read 1st character)

To accept the input, running it on the diagram must end at an accept state--o/w, reject!

Fix an alphabet for input strings (e.g. the abc's, {0,1}) & if L is precisely the set of strings some automaton accepts, L is a "regular language"

These languages rule b/c they're closed under all our fave operations--complement, union, intersection, concatenation, Kleene star

So far our automata are "deterministic"--meaning each state has exactly one outgoing arrow for each character in the alphabet

Non-deterministic automata can have any natural \\# of arrows w/ a given label & just need 1 run of the input to end at an accept state for it to accept

Every language accepted by a non-deterministic automaton is also accepted by a deterministic one--for ex., these two automata accept the same set of strings. In general, can build a deterministic equivalent automaton via a powerset construction.

Now let's switch to infinite inputs--instead of the automaton only accepting finite strings that end in an accept state, say the automaton accepts an infinite string if it enters an accept state infinitely often. Call these Buchi automata.

Note that as Buchi automata, these 2 no longer accept same inputs. In 2^N, the one on the left accepts the set of strings w/ infinitely many 0's, the one on the right accepts the set of strings w/ finitely many 1's.

Does the one on the right even have an equiv det. Buchi auto.?

It turns out that the classes of deterministic and non-deterministic Buchi automata do not recognize the same set of languages on any nontrivial alphabet. (There are other acceptance conditions one could impose to make those classes equivalent--see Muller automata, e.g.)

This automaton accepts a point in the interval [0,1] precisely if the ternary expansion of that point has either 0 or 2 as the coefficient for (1/3)^n for each n in N (Pretty sure there's a famous guy this set is named after?)

The connection of Buchi automata self-similar sets can be formalized by looking at "graph-directed iterated function systems," a common object of interest/tool of fractal geometry.

For example, the graph of this cantor distance function is recognized by a Buchi automaton.

Final note for set theory ppl: we can define Buchi Turing machines same way we define Buchi automata, & on a Cantor space the sets recognized by Buchi automata are effective $G_{delta}$, & the sets recognized by Buchi TMs are the effective analytic sets.

More we can say tho..?