Abstract
The idea behind orbit-finite sets is to allow, e.g. in a finite automaton or Turing machine, a set of states that is not strictly finite, but finite up to certain symmetries. These more general computational devices have many good properties of standard finite state devices, e.g. emptiness is decidable for orbit-finite automata or orbit-finite context-free grammars. However, there are new phenomena due to the symmetries. For example, deterministic and nondeterministic orbit-finite Turing machines have different expressive power, even when no constraints are placed on the running time.