Computability Theory (Quick Summary)

Computability Theory focuses on studying which problems can be solved by a Computer and which problems absolutely cannot (Decidability).

1. Turing Machine

The Turing Machine is a computational model designed by Alan Turing.

• It consists of an Infinite Tape (Memory that never fills up) and a Read/Write Head that can move forward and backward.
• It is considered the standard model that defines the word "Algorithm" (Any problem a Turing Machine can solve, any Computer in the world can also solve).

2. Decidability

Problems in Computer Science are categorized based on their solvability:

• Decidable Problem: Problems that have an Algorithm capable of finding an answer (Yes or No) and always stopping (Halt) within a finite amount of time.
• Undecidable Problem: Problems for which an Algorithm can never be created that covers all cases and guarantees finding an answer (Yes/No) and Halting 100% of the time.

3. Halting Problem

One of the most famous Undecidable Problems in Computer Science.

• Question: "Can we create a Program A that can check any Program B to see if, when run with Input C, Program B will stop running (Halt) or get stuck in an Infinite Loop?"
• Proof: Alan Turing proved using Contradiction that it is impossible to create this Program A.
• Conclusion: This reinforces to Programmers that Computers cannot solve every problem in the world (Computational Limit).