Section outline

  • Trovando, nel 1970, una specifica diofantea polinomiale di una relazione a crescita esponenziale, Yuri Matiyasevich stabiliva (grazie a un risultato di Julia Robinson di una ventina d'anni prima) che la stessa esponenziazione ammetteva una definizione esistenziale diofantea.

    Pertanto, grazie al teorema DPR che abbiamo visto la settimana scorsa, otteniamo che qualsiasi insieme enumerabile ricorsivamente è diofanteo polinomiale. Questo risultato, che rafforza DPR, viene chiamato teorema DPRM.

    Il risultato di Matiyasevich sfruttava come relazione a crescita esponenziale una relazione legata alla progressione di Fibonacci; però, subito, molti autori sostituirono a tale relazione un'altra legata alle soluzioni nei naturali di un'equazione di Pell della forma X^2=(a^2-1) Y^2+1 ove a è un intero >1. Questa presentazione alternativa fu seguita da molti autori sia statunitensi che sovietici e da ultimo fu impiegata da Julia Robinson e Yuri Matiyasevich in un articolo del 1975, cui si rifà la presentazione riportata qui sotto.    

    • L'esponenziazione in poche incognite File PDF

    • La lezione del 25 maggio si terrà da remoto in MS teams e inizierà alle ore 9 (senza quarto d'ora accademico).


      Chiunque fosse interessato, potrà poi partecipare a un seminario del prof. Omodeo sull'NP completezza che si terrà in Zoom a partire dalle 10:30 dello stesso giorno. (Contattare il docente per ricevere il link)