Computability

Concepts in Computer Science

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

What is computability?

Computable Problem

  • Algorithm Existence: A clear procedure exists.
  • Finite Time: Produces output in limited steps.

Non-Computable Problem

  • Algorithm Non-existence: Cannot solve this on all possible inputs.
  • Infinite Computation: May never reach a conclusion.
1 Non-Computable problems can become computable problems once we find an algorithm and/or make a known algorithm finish in finite time.
Concepts in Computer Science

Automata

Definition of Automata

  • Imaginary machines
  • Help us understand how computation works
  • Has states
  • Has rules to transition between states

An image of a traffic light as an analogy that represents automata

Concepts in Computer Science

Finite Automata (FA)

Finite Automata (FA)

  • Simple machines
  • Fixed number of states
  • No memory beyond current state

An image of a traffic light and states as an analogy for Finite Automata

Concepts in Computer Science

Pushdown Automata (PDA)

Pushdown Automata (PDA)

  • More powerful
  • Has states
  • Has stack based memory to make more complex decisions

An image of a traffic light and states as an analogy for Pushdown Automata

Concepts in Computer Science

Summary

Finite Automata (FA)

  • Useful for simple tasks

Pushdown Automata (PDA)

  • More powerful for more complex problems

Importance

  • If a problem can be modeled by automata, we CAN implement an algorithm to solve it
Concepts in Computer Science

Let's practice!

Concepts in Computer Science

Preparing Video For Download...