AFAIK, i numeri computabili di turing sono numeri il cui indice i-esimo può essere restituito da una macchina di Turing. Quindi un numero non computabile sarebbe qualcosa come un numero i cui punti decimali sono decisi se qualche altro programma si arresta su qualche altro input, ecc. Ma poi di nuovo, PI è un numero reale, che non può essere enumerato da un T.M. e quindi, non può essere calcolato? Quindi quale scuola di pensiero è corretta?PI è un numero computabile di turing?
risposta
Sì, π
è calcolabile. Ci sono alcune definizioni equivalenti di computable, ma la più utile qui è quella che hai dato sopra: un numero reale r
è computabile se esiste un algoritmo per trovare la sua cifra n
. Here è un tale algoritmo.
L'ultimo argomento non è valido; hai confuso la definizione "può trovare la cifra n
" con "può enumerare tutte le cifre". Quest'ultima non è una definizione utile: esclude anche tutti gli irrazionali e molti razionali!
Un fatto interessante è che i numeri computabili sono di fatto numerabili, poiché possiamo contare il numero di Godel delle macchine di Turing che li producono. Quindi quasi nessun real è computabile.
Penso che tu intenda che quasi tutti i numeri reali sono * non * calcolabili, poiché l'insieme delle macchine di Turing è numerabile. –
@larsmans: si, ovviamente =) – katrielalex
Grazie per averlo chiarito! Saluti! –
Non sono abbastanza sicuro di cosa intenda per "PI è un numero reale, che non può essere enumerato da un T.M.". Sì, i numeri reali non sono enumerabili, ma non vedo come questo influenzi il fatto che PI sia computabile. '4' è anche un numero reale, ma ciò non significa che non sia calcolabile. – sepp2k
Um, volevo dire, pensavo che ci sarebbe voluta un'infinitamente lunga Turing Machine per calcolare PI come lo stesso PI è infinitamente lungo. –
@Gaurav: con quell'argomento, ci vorrebbe una macchina di Turing infinitamente lunga per calcolare '1/3', poiché' 1/3 = 0.333333 ... 'è infinitamente lunga? – katrielalex