Automaton

Introduction to Theoretical Computer Science: Between Finite and Infinite - From Mathematical Theory to AI and Autonomous Driving

• It is something like a machine defined by a finite number of states and transitions.

  • There are an infinite number of “inputs that produce a certain output”.

• The key point is that finite formalisms, such as automata, can represent mathematical sets of infinity.

• The inclusion relationship of “inputs that produce a certain output” of automata can be proven with effort.

  • However, I want to confirm the inclusion relationship with finite computational power without proving it.
  • It is naturally impossible to check all the infinite number of inputs.
  • A method to strive for it with a finite number of computations
    • Ingredient 1: Empty set determination - whether there exists an input that produces a certain output (whether the set of inputs that produce a certain output is empty)
      • It is possible to verify with a finite number of checks by traversing the transition graph of the automaton and determining if it reaches a certain output.
    • Ingredient 2: Synchronous product of automata - like a composite function
    • Ingredient 3: Language inversion - like a complement
    • An infinite set A is included in an infinite set B if and only if the synchronous product of not B and A is empty.
      • Therefore, by determining if the synchronous product is empty, the inclusion can be determined.
    • The point is that with a finite number of empty set determinations, the inclusion relationship of an infinite number of sets can be confirmed.

• The limitations of finite automata

  • They have no memory capacity.
    • Because of this, there are input-output relationships that cannot be realized.
    • In other words, the set of “inputs that produce a certain output” is different from the set of “all inputs” in terms of infinite dimensions.
  • Turing machines were created to give automata memory capacity. (Might be incorrect) #Mathematics (Expert in Information Science)