Algoritmo
Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari. Il termine deriva dalla trascrizione latina del nome del matematico persiano al-Khwarizmi[1], che è considerato uno dei primi autori ad aver fatto riferimento a questo concetto. L'algoritmo è un concetto fondamentale dell'informatica, anzitutto perché è alla base della nozione teorica di calcolabilità: un problema è calcolabile quando è risolvibile mediante un algoritmo. Inoltre, l'algoritmo è un concetto cardine anche della fase di programmazione dello sviluppo di un software: preso un problema da automatizzare, la programmazione costituisce essenzialmente la traduzione o codifica di un algoritmo per tale problema in programma, scritto in un certo linguaggio, che può essere quindi effettivamente eseguito da un calcolatore.
Nel secolo scorso, il concetto di algoritmo venne formalizzato per risolvere il problema matematico della "decisione" (Entscheidungsproblem), posto da David Hilbert nel 1928, e altre successive formalizzazioni giunsero con lo sviluppo dei concetti di "calcolabilità effettiva" e di "metodo effettivo" . Le formalizzazioni matematiche più famose sono le funzioni ricorsive di Gödel–Herbrand–Kleene del 1930, 1934 e 1935; il Calcolo Lambda di Alonzo Church e la Formulation 1 di Emil Post del 1936; e, infine, la Macchina di Alan Turing del 1936–37 e 1939. Nonostante ciò, una definizione del concetto di algoritmo che sia formale e non tecnica manca tuttora  e si è pertanto costretti ad accontentarsi dell'idea intuitiva di algoritmo come una sequenza ordinata e finita di passi (operazioni o istruzioni) elementari che conduce a un ben determinato risultato in un tempo finito. 
La definizione di algoritmo appena riportata è piuttosto informale, mentre era necessario disporre di una definizione più rigorosa per trattare il concetto di algoritmo con strumenti matematici. Al tal fine sono stati definiti alcuni modelli matematici di algoritmo, fra i quali uno dei più celebri è la macchina di Turing. Essa rappresenta una sorta di computer ideale corredato di un programma da eseguire, ma, rispetto a un computer ideale, la macchina di Turing ha un funzionamento estremamente più semplice cosicché il suo funzionamento possa essere facilmente descritto in termini matematici, facendo uso di concetti come insieme, relazione e funzione. La macchina di Von Neumann, che è il modello di architettura sottostante a tutti i computer attuali, è equivalente, in termini di potere di calcolo, alla macchina di Turing. In altre parole, è stato dimostrato che un certo problema può essere risolto da un computer (opportunamente programmato) se e solo se esso può essere risolto anche da una macchina di Turing. Oltre alla macchina di Turing, proposta da Alan Turing nel 1936, nello stesso periodo altri matematici hanno elaborato diverse rappresentazioni formali del concetto di algoritmo, fra i quali ricordiamo, per esempio, il lambda calcolo. Dopo alcuni anni, emerse che tutti questi modelli erano equivalenti: i problemi che una macchina di Turing poteva risolvere erano gli stessi che poteva risolvere una macchina di von Neumann e anche gli stessi che poteva risolvere una funzione costruita col lambda calcolo inserire riferimento o citare risultato[senza fonte]. Da questi risultati, tra l'altro, scaturì la tesi di Church-Turing, che afferma che qualsiasi algoritmo sia modellabile con una macchina di Turing. In altri termini, questa tesi sostiene che è sostanzialmente impossibile cercare di immaginare un modello di algoritmo più potente e, di conseguenza, che nessuna macchina potrà mai risolvere problemi che una macchina di Turing non possa risolvere in linea di principio. Non si tratta di un teorema dimostrato matematicamente, poiché la tesi stabilisce l'eguaglianza di due concetti, l'algoritmo e la macchina di Turing, ma il primo non possiede una definizione formale. La tesi è oggi generalmente condivisa, sebbene i progressi nelle ricerche nel settore dell'ipercomputazione sembrino talvolta metterla in discussione.