Secondo la tesi di Church-Turing, i modelli matematici proposti dalla macchina di Turing dimostrano che tutti gli algoritmi possono essere risolti da tale metodologia

In questo articolo si parla di:

Risolvere dei problemi attraverso un’espressione matematica

Nei campi della matematica e dell’informatica, un algoritmo è definito come una sequenza finita di operazioni, o istruzioni, che vengono utilizzate per risolvere una classe specifica di problemi o per calcolare il risultato di una determinata espressione matematica. I primi riferimenti noti agli algoritmi si trovano in documenti che risalgono al XVII secolo a.C.. Si tratta dei papiri di Ahmes, noti anche come papiri di Rhind, che contengono una raccolta di problemi e le loro soluzioni. Uno di questi è un problema di moltiplicazione che lo scrittore afferma di aver copiato da altri papiri risalenti a due secoli fa.

Il concetto di algoritmo

L’algoritmo è un concetto fondamentale in informatica per due motivi. In primo luogo, costituisce la base della nozione teorica di computabilità, secondo la quale un problema è considerato computabile quando può essere risolto da un algoritmo. In secondo luogo, l’algoritmo è un concetto fondamentale nella fase di programmazione dello sviluppo del software. In questo contesto, la programmazione comporta la traduzione o la codifica di un algoritmo per un determinato problema in un programma per computer scritto in un linguaggio specifico. Ciò consente al problema di essere eseguito efficacemente da un computer, che ne rappresenta la logica di elaborazione.

La macchina di Turing e la macchina di Von Neumann: modelli di calcolo che ridefiniscono l’algoritmo

La definizione di algoritmo, in un periodo a cavallo tra gli anni ‘30 e ‘40, è stata ridiscussa utilizzando approcci matematici e modelli come la macchina di Turing e la macchina di Von Neumann. E’ stato dimostrato che tutti questi modelli sono equivalenti nel senso che possono risolvere gli stessi problemi. La macchina di Turing, proposta da Alan Turing nel 1936, è un modello di calcolo potente in quanto tutto ciò che può essere risolto da un computer può essere risolto anche dalla macchina di Turing, a condizione che sia programmata correttamente.

La tesi di Church-Turing: Il modello di calcolo di un algoritmo e la sua risoluzione

Questi risultati hanno portato alla formulazione della tesi di Church-Turing, che sostiene che ogni algoritmo può essere modellato da una macchina di Turing. Questo implica che nessuna macchina potrà mai risolvere problemi che una macchina di Turing non possa risolvere. In sostanza, il teorema implica che la macchina di Turing rappresenta un modello di calcolo essenzialmente impossibile da superare in termini di potenza. In altre parole, è essenzialmente impossibile prevedere un modello più potente di un algoritmo e, di conseguenza, nessuna macchina sarà mai in grado di risolvere i problemi che una macchina di Turing può risolvere. La tesi è oggi generalmente accettata, anche se i progressi della ricerca nel campo dell’ipercalcolo sembrano talvolta metterla in discussione. Esiste anche l’algoritmo di Hirschberg, dal nome del suo creatore, Dan Hirschberg, che nella programmazione dinamica trova l’allineamento ottimale della sequenza tra due stringhe.

Author: Claudia Sistelli

© Riproduzione Riservata