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.
- 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)
-
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)
- They have no memory capacity.