Ordinateur
Les logiciels informatiques sont des listes (généralement longues) d’instructions exécutables par un ordinateur. De nombreux programmes contiennent des millions d’instructions, effectuées pour certaines de manière répétitive. De nos jours, un ordinateur personnel exécute plusieurs milliards d’instructions par seconde. Depuis le milieu des années 1960, des ordinateurs exécutent plusieurs programmes simultanément. Cette possibilité est appelée multitâche. C’est le cas de tous les ordinateurs modernes. En réalité, chaque cœur de processeur n’exécute qu’un programme à la fois, passant d’un programme à l’autre chaque fois que nécessaire. Si la rapidité du processeur est suffisamment grande par rapport au nombre de tâches à exécuter, l’utilisateur aura l’impression d’une exécution simultanée des programmes. Les priorités associées aux différents programmes sont, en général, gérées par le système d'exploitation.
Informatique
Tous les modèles de calcul étant équivalents, ce résultat s'applique aussi aux autres modèles, ce qui inclut les programmes et logiciels que l'on peut trouver dans les ordinateurs courants. Il existe un lien très fort entre les fonctions que l'on ne peut pas calculer et les problèmes que l'on ne peut pas décider (voir Décidabilité).