A Long and Exciting Day
Yesterday was a rather long day — or to put it more precisely, it became a long day, when Manitou (Jérémy) and I decided to attend a lecture about Models and Logic (the course is called dModLog at DAIMI). We had started our day at 8 O’clock and was finished five hours later. But then we decided to go to the lecture — it lasted for another three hours.
The lecture was really interesting, we heard about Finite Automata, which I believe is also called Finite State Machines. We heard about languages and how to define a Finite Automata in terms of five parameters: Q, Σ, δ, q0, and F:
Q is a finite set of states. The states are the memory of the machine, and in any given moment, the machine will be in exactly one of the states.
Σ is a finite input alphabet. It could be binary digits, the ASCII characters or another finite set of symbols.
δ is a transition function δ: Q×Σ → Q. δ is the function that makes the machine act on it’s input.
q0 ∈ Q is the start state of the machine, and
F ⊆ Q is the set of final, accepting states. If the machine is in a state in F, then it will answer “Yes”, if not, then it will answer “No”.
You can take a look at the slides that were used if you want to know more. I hope to be able to follow the lectures loosly, as they’re going to prove Gödel’s incompleteness theorem later. Ever since I first heard about it, I’ve wanted to understand what it really says — I’ve only heard the informal explaination of it, namely that it says, that there are things in every closed system that cannot be proved, although they’re known to be true. That sounds like a very fundamental theorem, and I’m really looking forward to learning about it — if not this year, then definitely next year, where dModLog will be part of our mandatory courses.
Leave a comment