Die Unterscheidung zwischen Hardware und Software ist grundlegend für moderne Computer und ihre universelle Verwendbarkeit. Dieser Unterscheidung liegt eine einfache, aber überraschende Idee zugrunde: die Idee der universellen Turing-Maschine oder Registermaschine. Formale Modelle der Berechenbarkeit wurden im Jahre 1936, lange bevor moderne Computer auch nur erträumt waren, von Alan Turing (1912-1954) als Abstraktion des menschlichen Berechnungsprozesses erfunden. Die formale Theorie dieser Maschinen erlaubt es uns, Berechenbarkeit und ihre Grenzen mathematisch und präzise zu untersuchen und bildet die Grundlage für die modernen Begriff von Berechnungskomplexität.