Suite au premier article sur la Machine de Turing, l’auteur réfléchit, dans celui-ci, à la notion de complexité algorithmique. Celle-ci mesure la quantité de ressources (temps ou espace mémoire) consommée pour résoudre un problème. Là où la calculabilité détermine si on peut le faire en théorie, la complexité en précise le coût, autrement dit si on peut le faire en pratique. Ce déplacement de problématique conduit à des questions fondamentales dont la plupart sont ouvertes. On pourrait penser a priori que cela dépend du dispositif (de la machine) utilisé. C’est bien entendu exact d’un certain point de vue. Mais on va voir que l’on peut définir une notion de complexité (asymptotique) qui ne dépend pas de la machine utilisée. La plupart des questions qui se posent alors pour cette complexité (comme le fameux problème « P est-il égal à NP ? ») ne sont pas résolues. Et elles sont fondamentales.
L’auteur s’intéresse, tout d’abord, à la complexité en temps. Le coût en temps d’une machine de Turing déterministe appliquée à une entrée donnée w est égal au nombre de changements d’états que fait la machine pour arriver à un état final. Il se limite à des entrées w pour lesquelles ce nombre de changements d’états est fini. L’auteur juge, que dans ce contexte, il est judicieux de « se limiter » à un type particulier de machines de Turing. Ces machines de Turing ont deux états finaux : un état d’acceptation et un état de refus.