Bookmark: https://www.youtube.com/watch?v=9syvZr-9xwk

Finite Automata

Regular Expression

Deterministic finite automaton (DFA)

Alan Turing said only 5 things needed for a computer to do “anything”:

  1. move left one location
  2. move right one location
  3. read symbol at current location
  4. print 0 at current location
  5. print 1 at current location

Lambda calculus and the Turing machine are fundamental models of computing and theoretically equivalent.

Computability Theory

Reduction

Halting Problem

Halting problem is a decision problem Proven to be undecidable, which means there is no program that can solve the halting problem for general enough computer programs

“In 1936, Alan Turing proved that the halting problem over Turing machines is undecidable using a Turing machine; that is, no Turing machine can decide correctly (terminate and produce the correct answer) for all possible program/input pairs.”

Models of Computation

Finite-state machine

Model of computation is a model that describes how an output of a mathematical function is computed given an input.

  • Sequential models
    • Finite state machines
    • Pushdown automata
    • Turing machine
  • Function models
    • Lambda calculus
    • Recursive functions
    • Combinatory logic
    • Abstract rewriting systems
  • Concurrent models
    • Cellular automaton
    • Kahn process networks
    • Petri nets
    • Synchronous Data Flow
    • Interaction nets
    • Actor model

Church-Turing thesis

Church-Turing thesis is the computability thesis

Automata Theory