Comments in response to:
Commenti in risposta a:
this post / questo post:
io non sono un matematico, però "un calcolatore ideale che è matematicamente ben definito e dal funzionamento deterministico" mi suona male, una MT può essere tranquillamente deterministica o meno.
riffraff • 3/21/06; 11:57:04 PM #

ahimé, temo che piú che un matematico qui ti occorra un informatico teorico. l'idea stessa di una dimostrazione senza un insieme di assiomi alle spalle (cos'è, *esattamente*, una tm?) mi lascia un po' stranito. qual è la definizione precisa di "funzione calcolabile"? a me sembra che dire che nessuna funzione scrivibile da una tm cresca piú velocemente di bb sembra vagamente tautologico. per esempio: f(x):=x^x è una funzione calcolabile o no?
delio • 3/22/06; 10:36:26 AM #

Adesso non ho tempo, però provo a rispondervi. @riffraff: a parte l'incertezza nella definizione di TM dovuta ad esigenze di brevità (ma su Wikipedia che ho linkato c'è la def. matematica precisa) la TM è deterministica, cioè a input uguali corrispondono output uguali. Si possono introdurre non determinismi (se vai a vedere è stato fatto) ma nella TM standard non ci sono. @delio: purtroppo è solo la traccia di una dimostrazione. Calcolabile in questo caso significa che è riproducibile da un algoritmo (da una TM) f(x) = x^x è calcolabile se x è un numero naturale (ma anche un razionale) non lo è se è un reale trascendente perché non esiste rappresentazione finita del numero. Però qui parliamo di naturali. Comunque l'articolo originale di Rado è qua: Tibor Rado, "On Non-Computable Functions," Bell System Technical Journal, vol. XLI, no. 2, May 1962, pp. 877- 884.
Massimo Morelli • 3/22/06; 10:59:51 AM #

confermo che deve passare un informatico (teorico) e non un matematico. In teoria io dovrei anche esserlo, ma sono più di quindici anni che ho smesso... Per una definizione (inglese) di funzione computabile suggerisco MathWorld. Se non erro, una funzione computabile (sempre da N a N) è una funzione per cui puoi trovare in tempo finito il suo valore per un qualunque numero. In effetti avremmo potuto tradurre Busy Beaver come Passera Impegnata :-)
.mau. • 3/22/06; 11:21:30 AM #

massimo: ah, grazie per la precisazione ora capisco cosa intendevi per non deterministico, io facevo appunto riferimtno al comportamento interno della macchina
riffraff • 3/22/06; 4:48:14 PM #

che nostalgia. la mia passione per la scienza e' nata proprio sfogliando dei Le Scienze dei primi anni '80. per cui, l'Alacre Castoro e' stata una delle prime cose che hanno acceso il mio interesse.
dr.psycho • 3/25/06; 12:07:14 PM #

Dr. ti facevo più giovane.
Massimo Morelli • 3/26/06; 6:40:56 PM #