Che ne dite della MACCHINA DI TURING?
Aprirei una discussione critica sulla Macchina d Turing semplicemente perchè, credo che, soffiando nelle orecchie di chi me le porgesse, l'idea, forse scontata, che la "Macchina" dica molto di più con ciò che sembrano essere i suoi punti deboli che con ciò che dimostra.
Lascio a chiunque lo voglia, l'iniziativa di cominciare.
mario1
Lascio a chiunque lo voglia, l'iniziativa di cominciare.
mario1
Risposte
la seguente precisazione fatta dall'amico del precedente post, molto tempo fa:
"Quindi parlare di fisica degli oggetti logici richiederebbe quanto meno di darne una definizione, cosa molto difficile se non si accetta il concetto che questi oggetti "logici", qualunque cosa essi siano, pre esistono e ci limitiamo a riscoprirli.
Comunque ogni opinione è rispettabile, il mio punto di vista e che la critica alla matematica vada fatta nel linguaggio della matematica.
Saluti"
Merita una mia risposta, seppure ritardataria.
Per "oggetti logici" intendo gli oggetti. diciamo pure, "del pensiero", cioè quegli oggettti e, se si vuole, quella parte di universo, che la buonanima di Cartesio denominava come "Res Cogitans", per distinguerla dal resto dell'universo che chiamava "res extensa". Peccato che la buonanima pensasse le due aree come separate da una demarcazione netta e non sfumata, come , in effetti, è.
"Quindi parlare di fisica degli oggetti logici richiederebbe quanto meno di darne una definizione, cosa molto difficile se non si accetta il concetto che questi oggetti "logici", qualunque cosa essi siano, pre esistono e ci limitiamo a riscoprirli.
Comunque ogni opinione è rispettabile, il mio punto di vista e che la critica alla matematica vada fatta nel linguaggio della matematica.
Saluti"
Merita una mia risposta, seppure ritardataria.
Per "oggetti logici" intendo gli oggetti. diciamo pure, "del pensiero", cioè quegli oggettti e, se si vuole, quella parte di universo, che la buonanima di Cartesio denominava come "Res Cogitans", per distinguerla dal resto dell'universo che chiamava "res extensa". Peccato che la buonanima pensasse le due aree come separate da una demarcazione netta e non sfumata, come , in effetti, è.
Brevemente: per fisica degli oggeti logici, qui si vuol intendere la matematizzazione (cioè l'applicazione della matematica) agli oggetti "del pensiero" vale a dire di quegli oggetti che Cartesio comprendeva nell'insieme detto Res gogitans.
Forse intendeva dire che una TM multinastro puo' essere simulata
da una TM a doppio contatore
Un piccolo OT: questo forum secondo me e' troppo poco moderato.
Non dico di dotarlo di cani da guardia, pero' chiudere qualche topic in piu'
alzerebbe il livello del forum. Ad esempio la sezione Informatica
andrebbe chiusa quasi tutta
da una TM a doppio contatore
Un piccolo OT: questo forum secondo me e' troppo poco moderato.
Non dico di dotarlo di cani da guardia, pero' chiudere qualche topic in piu'
alzerebbe il livello del forum. Ad esempio la sezione Informatica
andrebbe chiusa quasi tutta
Ragazzi, è evidente che questo MassimilianoVen è un altro disturbatore alla Sandokan e co.
D'altra parte, chiamare una Macchina di Turing "struttura algebrica" è davvero un misero tentativo, in relazione all'inventarsi teoremi non esistenti
D'altra parte, chiamare una Macchina di Turing "struttura algebrica" è davvero un misero tentativo, in relazione all'inventarsi teoremi non esistenti
"MassimilianoVen":
A questo proposito io propongo di studiare la congettura di Svozil, che "boccia le strutture algebriche commutative"...
Di cosa si tratta, esattamente? In internet non ho trovato niente..
mi ricordo un'importante Teorema:
"Ogni macchina di Turing è una struttura algebrica isomorfa a quella costituita da 2 contatori"
Quindi caratterizziamo il calcolo con la logica e possiamo sostituire il conteggio in molte occasioni!
A questo proposito io propongo di studiare la congettura di Svozil, che "boccia le strutture algebriche commutative"...
"Ogni macchina di Turing è una struttura algebrica isomorfa a quella costituita da 2 contatori"
Quindi caratterizziamo il calcolo con la logica e possiamo sostituire il conteggio in molte occasioni!
A questo proposito io propongo di studiare la congettura di Svozil, che "boccia le strutture algebriche commutative"...
quote:
Originally posted by mariodic
1) L'Osservatore è unico
2) L'Osservatore è un insieme di eventi dell'universo organizzato in sistema dalla entità singolare unica detta "IO"
3) L'osservabile è un insieme generatore di eventi, anch'esso organizzato dalla singolarità "IO", che genera eventi "favorevoli" all'IO" con una probabilità attesa "p"
4) Il sistema composto da (2) e da (3) è finalizzato ad accrescere la probabilità "p" (processo conoscitivo: in pratica il sistema mira a ridurre la sua entropia interna).
Continuo a ribadire, con rispetto, che non ti capisco e che questo è probabilmente è un mio limite. Ti ringrazio comunque per la cortese pazienza con cui rispondi.
In ogni caso quelle che hai scritto sopra non sono definizioni matematiche ma tutt'al più fisiche-filosofiche.
Quello che mi aspettavo era una definizione basata sugli assiomi di Zermelo-Fraenkel, o su quelli di Peano dei interi o su qualunque insieme di regole che consente di fondare le nostre conoscenze matematiche, magari un po' adattati alla esigenza di introdurre l'osservatore.
Pertanto, non sono in grado di sostenere questa discussione che esula dal mio bagaglio di conoscenza.
Comunque in tutto questo manca l'aspetto costruttivo, insomma tutto questo a cosa serve? dov'è il valore aggiunto? e come si materializzano matematicamente le differenze tra due teorie una con e una senza "osservatore"?.
Saluti
Mistral
quote:
Detto questo ciò non toglie che tu abbia la tua definizione matematica di osservatore basata sui concetti di insieme, relazione, funzione etc..., solo che se non la espliciti io non ti capisco, comunque sono conscio che è un mio limite e questo non è poco[:)].
Saluti
Mistral
Banner pubblicitario McAfee permettendo, proverò a definire l'Osservatore come avevo promesso nel mio precedente intervento.
Premetto innanzitutto che questa definizione viene elaborata dall'"interno" del sistema "Osservatore" e non dall'esterno come da tradizione, questo perchè occorrerebbe un super Osservatore "esterno" che osservasse l?osservatore interno, ciò è assurdo dal momento che l'Osservatore è unico. Dunque:
1) L'Osservatore è unico
2) L'Osservatore è un insieme di eventi dell'universo organizzato in sistema dalla entità singolare unica detta "IO"
3) L'osservabile è un insieme generatore di eventi, anch'esso organizzato dalla singolarità "IO", che genera eventi "favorevoli" all'IO" con una probabilità attesa "p"
4) Il sistema composto da (2) e da (3) è finalizzato ad accrescere la probabilità "p" (processo conoscitivo: in pratica il sistema mira a ridurre la sua entropia interna).
NOTA:
Per definire la singolarità IO "dall'interno" del sistema (4) = (2)+(3) considereremo il sistema (2)+(3) partendo dall'accezione più estesa: l'intero universo, restringendolo progressivamente, analogamente a quanto fece Euclide che per definire l'entità limite del punti "spoglio" progressivamente l'entità geometrica tridimensionale sopprimendo, una alla volta, l'altezza, la larghezza e la profondità e chiamò "punto" quel che rimaneva.
Nel caso della singolarità "IO" il procedimento è il seguente (che si svolge dall'interno del sistema (2)+(3):
a) L'Osservatore riduce il sistema (2)+(3) eliminando l'osservabile (3) e sostituendolo con un sott'insieme di (2) che indicheremo con (3'). Dunque l'Osservatore "osserva" una parte di ste stesso: l'osservabile (3')
b) L'Osservatore elimina l'osservabile (3') e lo sostituisce con sott'insieme di (2)-(3')=(3") e così progressivamente.
c) L'Osservatore definisce l'IO come il limite del processo di riduzione (a), (b).
C'è spazio per filosofare su questo "limite" ma non è necessario per i fini che qui ci interessano
A) Sia x=X(p) una funzione arbitraria decrescente, motona e continua della probabilità "p" tale che il suo limite per p-->0 = infinito e limite per p-->1 = 0; associamo ad ogni X(p) l'insieme di tutti i sistemi "osservabili" (per intenderci: del tipo (3)) che l'Osservatore stima producano una evidenze di valore a lui "favorevoli" uguale a p
(NOTA: per "evidenza di un valore"
-favorevole o no all'Osservatore- intendesi qualsiasi valore del tipo, per esempio, "testa" o "croce", la dove testa o croce sia la evidenza reputata favorevole dall'Osservatore.)
B) La semiretta positiva (A) è una coordinata di una spazio che qui chiameremo "della conoscenza": essa ordina tutti i sistemi o sottosistemi generatori di eventi che costituiscono l'universo (cioè sistemi osservabili del tipo (3)) per ordine di conoscenza da parte dell'IO.
NOTA: nel primissimo tratto più prossimo all'origine della semiretta, si raccolgono gli eventi più certi in assoluto per l'IO"; questi possono considerarsi gli elementi minimi di costruzione dell'intero universo, per esempio le entità logiche come, per esempio, enti relazionali come "maggiore" o "minore" oppure il concetto matematico di "unità" o quello di "iterazione", ecc.; all'altro capo della retta, al limite di x --> infinito, vi sono eventi possibili ma di probabilità zero. Il concetto di iterazione, appena citato tra quelli più prossimi all'origine della semiretta, è, per inciso, molto importante perchè può essere (non necessariamente) scelto come un'altra coordinata per completare lo "spazio" della conoscenza, ma in questa fase non è importante.
-----------------
Le difinizioni di oggetti di un sistema, fatte dall'interno del sistema stesso, non hanno quell'asciutezza e rigore (solo apparenti però) che hanno le definizioni di enti di sistemi che l'osservatore osserva dall'esterno (ammesso che ciò sia possibile ad un osservatore esterno vedere l'interno di un sistema senza entrarci)
mario1
quote:
Quindi mi permetto di ribadire che leggendo i lavori tecnici sulla macchina di Turing non c'e' proprio spazio per l'osservatore che tu cerchi, che è molto più legato al fatto di spiegare la macchina di Turing senza usare troppa matematica. Pertanto i termini quali "leggere", "scrivere", "scorrere", "arrestarsi" etc..che pur suggeriscono l'esistenza di un osservatore che guarda e interagisce, possono essere fatti corrispondere uno ad uno con definizioni matematiche basate sul concetto di funzione, relazione, insieme etc....
Detto questo ciò non toglie che tu abbia la tua definizione matematica di osservatore basata sui concetti di insieme, relazione, funzione etc..., solo che se non la espliciti io non ti capisco, comunque sono conscio che è un mio limite e questo non è poco[:)].
Saluti
Mistral
Che non si sia mai dato spazio all'Osservatore è proprio quello che lamento ed è il motivo che ho aperto la discussione sulla MdiT.
Se non vi fosse l'Osservatore né la matematica né altro dell'universo esisterebbe.
Quanto alla definizione di Osservatore mi sono in più occasioni intrattenuto in questo stesso forum, ma vedo che è necessario che vi ritorni. Era mia intenzione farlo questa sera ed avevo cominciato a scrivere in proposito, se non che mi è saltato per ben due volte la finestra di scrittura a lavoro avanzato, il tutto a causa di un dannato banner della McAfee mi sta disturbando ripetutamente. Spero di ritornarci domani sera.
Scusami
mario1
quote:
Originally posted by mariodic
I motivi per cui ho proposto l'apertura, in questo forum, di una discussione sulla MdiT, non sono quelli di ripassare ciò che molti autorevoli commendatori hanno scritto, ma di quello che non hanno scritto. In effetti nessuno di essi, per quanto mi risulta, avrebbe preso in considerazione il ruolo dell'Osservatore, che, come mi propongo di dimostrare, è niente meno, che regista e primo ed unico attore di tutta la scena.
Ti ho scritto in un mio post precedente "citando" il lavoro matematico di altri matematici, che già lo stesso Turing ha concepito una teoria detta "degli oracoli", in cui l'ipotetico computer se fermava per prendere uno o più suggerimenti dall cosidetto oracolo e quindi ripartiva. Questo modellizza in qualche maniera l'interazione che nel mondo reale avviene tra la macchina e l'uomo.
quote:
Ora mi propongo di dimostrare che l'Osservatore non può essere disgiunto dalla MdiT (come da qualsiasi computer reale) e forma, con la macchina, un sistema a sé.
....
Il punto è che se si leggono dei lavori di Matematica non divulgativi sulle teorie di Turing e Godel si vede che molte cose avvolte da quell'alone di fascino sono in realtà, per chi ha un background matematico universitario (ingegneri, fisici, informatici, matematici), semplici concetti esprimibili con funzioni, insiemi e relazioni etc... Dove sta la novita quindi? semplicemente nel modo in cui questi concetti sono combinati in definizioni e nei conseguenti teoremi.
Quando questi concetti sono letti su libri di Penrose, Davies e di molti altri che hanno fatto e loro enormi fortune scrivendoli, si tende a passare al lettore un entusiasmo eccessivo. Il realtà non dovrebbe sfuggire il fatto che il percorso naturale è sempre quello:
teoria matematica A->interpretazione/critica filosofica->teoria matematica B
Il fatto che per divulgare il concetto di macchina di Turing si dica che il "il nastro è scritto", "la macchina legge", "la macchina si arresta" non vuol dire che che ci sia qualcuno o qualcosa che effettivamente legge, scrive o si arresta, tanto meno qualcuno che osserva il tutto e interagisce. Personalmente la definirei "orpellatura divulgativa" molto tipica nei libri scritti dai fisici, solo che fintanto che parlano di fenomeni fisici la cosa funziona bene. Quando si parla di matematica è molto più difficile e si finisce facilmente per fare pentoloni di minestrone in cui sobbollono concetti matematici, fisici e filosofici affiorando in superficie in maniera randomica, oddio! un orpello divulgativo [:o)] ci sono cascato pure io.
Quindi mi permetto di ribadire che leggendo i lavori tecnici sulla macchina di Turing non c'e' proprio spazio per l'osservatore che tu cerchi, che è molto più legato al fatto di spiegare la macchina di Turing senza usare troppa matematica. Pertanto i termini quali "leggere", "scrivere", "scorrere", "arrestarsi" etc..che pur suggeriscono l'esistenza di un osservatore che guarda e interagisce, possono essere fatti corrispondere uno ad uno con definizioni matematiche basate sul concetto di funzione, relazione, insieme etc....
Detto questo ciò non toglie che tu abbia la tua definizione matematica di osservatore basata sui concetti di insieme, relazione, funzione etc..., solo che se non la espliciti io non ti capisco, comunque sono conscio che è un mio limite e questo non è poco[:)].
Saluti
Mistral
quote:
Contrariamente a quanto ti sembra di ricordare in merito ai tempi di arresto della Macchina di T., la dimostrata esistenza di uno stato di "indecidibilità" (Godel) fa sì che esistono proposizioni di cui, a priori, è possibile stabilire la verità o la falsità ed altre in cui non è possibile; si tratta del problema della "indecidibilità".
Forse non mi sono spiegato bene, sono due cose diverse le seguenti:
1)Non si arresta mai
2)Non si arresta entro un numero di passi t prefissato (il numero di passi è una misura del tempo)
Tutto questo per il semplice fatto che ad esempio la classe dei programmi (nastri finiti) che per una data macchina non producono arresto entro t, contiene la classe dei programmi che producono arresto entro t+1 etc...
Allora io ho affermato che mi sembra di ricordare che 2) è un problema risolubile. Mentre fin dal primo post ho chiarito che 1) non lo era. Per carità poi può essere che ricordo male e anche 2) non è risolubile, pero ciò non toglie che 1) e 2) siano concetti distinti. Per altro per t piccoli è intuitivo che il problema 2) sia risolubile. Ma attenzione t è fissato, t diverso problema diverso, il fatto la famiglia infinita di problemi con t parametro sia una famiglia di problemi tutti risolubili, sfortunatamente non consente di risolvere il problema 1).
Saluti
Mistral
La MdiT è un computer ideale che schematizza qualsiasi computer reale . Questo ideale computer, immaginato da Turing dopo che Godel elaborò la sua famosa dimostrazione sulla esistenza di proposizioni indecidibili, debellava l'antica quasi certezza che, dato un sistema di assiomi e di regole algoritmiche, una qualsiasi proposizione, formulata nell'ambito di questo sistema, potesse essere provata come vera oppure come falsa e basta. Agli inizi del '900 questa dimostrazione fu un terremoto per alcuni e una delusione per altri. Sull'eco di quell'onda fu immaginata la MdiT che semimaterializzava la prova di Godel.
I motivi per cui ho proposto l'apertura, in questo forum, di una discussione sulla MdiT, non sono quelli di ripassare ciò che molti autorevoli commendatori hanno scritto, ma di quello che non hanno scritto. In effetti nessuno di essi, per quanto mi risulta, avrebbe preso in considerazione il ruolo dell'Osservatore, che, come mi propongo di dimostrare, è niente meno, che regista e primo ed unico attore di tutta la scena.
Ricordo che una proposizione, esaminata nel rigoroso ambito del suo sistema di assiomi e di regole, si riteneva poterne dimostrare la verità o la falsità. Godel,invece, dimostrò che ciò non era vero, nel senso che c'era una terza alternativa: la impossibilità logica di pervenire a l'una o l'altra conclusione, una situazione di indecidibilità, appunto.
Turing immagina la sua macchina che, ripercorrendo gli algoritmi, presuntamente finiti nel numero, giunga a dimostrare la validità o meno di una proposizione definita nel sistema in esame.
La MdiT ha una testina. mobile rispetto ad un nastro infinito, in cui l'Osservatore ha scritto un programma, di lunghezza finita, che contiene la sintesi di tutte le regole e gli assiomi del sistema in osservazione in modo che, setacciando tutti i percorsi logici consentiti (ovviamente anch'essi in numero finito come finito è il numero degli essiomi e delle regole algoritmiche descriventi il sistema) puo verificare la validità o la contradittorietà della proposizione in analisi.
Ora mi propongo di dimostrare che l'Osservatore non può essere disgiunto dalla MdiT (come da qualsiasi computer reale) e forma, con la macchina, un sistema a sé.
Cos'è l'Osservatore? Non è una persona qualsiasi, come qualcuno potrebbe pensare, ma un sistema che fa capo all'"IO"; tuttavia, per i fini della dimostrazione che mi sono proposto, mi permetto di non indugiare intorno alla questione dell'"Osservatore universale", argomento, per altro, discusso altrove in questo stesso forum, per accettare, in prima approssimazione, che l'Osservatore sia un qualsiasi operatore umano che gorverni la MdiT, giusto come si aspetta un comune lettore di queste note.
Intanto cominciamo col prendere atto che questo Osservatore ha scritto il programma, contenuto nella testina della MdiT e i dati di partenza del programma (sul nastro o sulla stessa testina), e, quindi conosce il sistema, inoltre deve decidere quando e come aviare la macchina. Come si vede, non si tratta di cose di poco conto.
Dopo l'inizio del funzionamento della macchina ecco cosa ci si aspetterebbe:
1) La macchina deve fermarsi, e lo fa entro un tempo finito, fornendo sull'output la relativa informazione sulla verità o meno della proposizione da analizzare:
2) La macchina non è in grado di appurare se la proposizione è vera o falsa perchè nessuno dei percorsi logici consentiti dal sistema e, quindi, dal programma della macchina, ricostruisce la proposizione o una sua contraddizione; la macchina, dunque non si ferma e continua la sua vana ricerca.
Attenzione, ora, mentra la macchina lavora, cosa fa l'Osservatore? Diciamo che aspetta per vedere se e quando si fermerà la testina e, se si fermerà e leggere l'utput dell'esito. Se nonchè, il povero Osservatore, non sapendo a priori se e quando si fermerà la macchina, deve necessariamente stabilire in anticipo un tempo massimo di attesa e sperare di essere fortunato per godersi almeno l'arresto della macchina; mai il tempo da destinare all'attesa deve essere commisurato, sempre dall'Osservatore, all'"importanza" del problema stesso (questa variabile, ignorata dagli scritti ufficiali sulla MdiT, rappresenta cio che genericamente si definisce "insieme delle condizioni ambientali").
L'osservatore, come si vede, è ben più che uno spettatore neutrale di pre-quantistica memoria, ma un regista e primo attore e, soprattutto, rappresenta l'intero universo (condizioni ambientali) che interagisce olisticamente con l'osservabile, che non è la MdiT (o altro computer) ma la proposizione logica che si vuol verificare (quindi, questo è un esempio in cui un oggetto logico viene trattato in pieno come un oggetto fisico. Ciò con buona pace di chi, in questo forum, ha trovato questa mia affermazione, o similitudine tra oggetti della fisica e oggetti della matematica e della logica, una risibile fantasticheria da filosofi).
L'osservatore, in conclusione, diviene parte di un sistema che, fra gli altri strumenti, contiene "anche" la MdiT e, per quanto si è detto a proposito del tempo da "destinare" all'attesa di un possibile arresto della testina. Va da se che egli, che sintetizza il sistema di osservazione, emetta una sentenza di "INDECIDIBILITA'" anche per un problema che, nella più ingenua conclusione storica sulla MdiT, sarebbe stato decidibile.
mario1
quote:
......
"la fisica degli oggetti logici"
.....
Scusa mi era sfuggita, questa gustosa definizione.
Comunque si scofina nella filosofia, guai ai filosofi che vogliono fare i matematici! esistono svarioni scritti dal grandissimo Popper sulla matematica, che sono stati tra l'altro oggetto di un'articolo di le Scienze di qualche anno fa. Putroppo la matematica va praticata prima di filosofarla, altrimenti la mente umana con la sua enorme fantasia e immaginazione, viola il rigore della struttura ipotesi-tesi-dimostrazione e rincorre fantasmi.
60 e dividibile per 2,3,4,5,6...è divisibile per tutti gli interi?
Le equazioni di 2°,3°,4°....grado sono risolubili per radicali allora lo sono quelle di qualsiasi grado?
No, esiste qualche signicato "fisico" in questo? per me no, per me è come il fatto che esistono numeri razionali con rappresentazione decimale periodica in una base e rappresentazione decimale finita in un'altra base.
Il tuo punto di vista e che gli oggetti matematici hanno esistenza a se stante e vengono scoperti dall'uomo, o vengono inventati dalla mente umana. La matematica si scopre o si inventa?
Anche se si possono citare numerosi esempi di teorie matematiche suggerite dalla natura, sono decisamente molte di più le teorie matematiche che non hanno tutt'ora nessun utilizzo pratico, eppure sono bellissime da studiare e comprendere.
Quindi parlare di fisica degli oggetti logici richiederebbe quanto meno di darne una definizione, cosa molto difficile se non si accetta il concetto che questi oggetti "logici", qualunque cosa essi siano, pre esistono e ci limitiamo a riscoprirli.
Comunque ogni opinione è rispettabile, il mio punto di vista e che la critica alla matematica vada fatta nel linguaggio della matematica.
Saluti
Mistral
PS non capisco il tuo riquotare il mio post precendent, se ho detto qualche emerita castroneria, cosa che capita frequentemente sigh!, fammela notare può darsi che "non sappia di non sapere" ops! filosofia![:o)]
quote:
Originally posted by Mistral
quote:
Contrariamente a quanto ti sembra di ricordare in merito ai tempi di arresto della Macchina di T., la dimostrata esistenza di uno stato di "indecidibilità" (Godel) fa sì che esistono proposizioni di cui, a priori, è possibile stabilire la verità o la falsità ed altre in cui non è possibile; si tratta del problema della "indecidibilità".
Forse non mi sono spiegato bene, sono due cose diverse le seguenti:
1)Non si arresta mai
2)Non si arresta entro un numero di passi t prefissato (il numero di passi è una misura del tempo)
Tutto questo per il semplice fatto che ad esempio la classe dei programmi (nastri finiti) che per una data macchina non producono arresto entro t, contiene la classe dei programmi che producono arresto entro t+1 etc...
Allora io ho affermato che mi sembra di ricordare che 2) è un problema risolubile. Mentre fin dal primo post ho chiarito che 1) non lo era. Per carità poi può essere che ricordo male e anche 2) non è risolubile, pero ciò non toglie che 1) e 2) siano concetti distinti. Per altro per t piccoli è intuitivo che il problema 2) sia risolubile. Ma attenzione t è fissato, t diverso problema diverso, il fatto la famiglia infinita di problemi con t parametro sia una famiglia di problemi tutti risolubili, sfortunatamente non consente di risolvere il problema 1).
Saluti
Mistral
mario1
quote:
Contrariamente a quanto ti sembra di ricordare in merito ai tempi di arresto della Macchina di T., la dimostrata esistenza di uno stato di "indecidibilità" (Godel) fa sì che esistono proposizioni di cui, a priori, è possibile stabilire la verità o la falsità ed altre in cui non è possibile; si tratta del problema della "indecidibilità".
Forse non mi sono spiegato bene, sono due cose diverse le seguenti:
1)Non si arresta mai
2)Non si arresta entro un numero di passi t prefissato (il numero di passi è una misura del tempo)
Tutto questo per il semplice fatto che ad esempio la classe dei programmi (nastri finiti) che per una data macchina non producono arresto entro t, contiene la classe dei programmi che producono arresto esattamente a
Allora io ho affermato che mi sembra di ricordare che 2) è un problema risolubile. Mentre fin dal primo post ho chiarito che 1) non lo era. Per carità poi può essere che ricordo male e anche 2) non è risolubile, pero ciò non toglie che 1) e 2) siano concetti distinti. Per altro per t piccoli è intuitivo che il problema 2) sia risolubile. Ma attenzione t è fissato, t diverso problema diverso, il fatto la famiglia infinita di problemi con t parametro sia una famiglia di problemi tutti risolubili, sfortunatamente non consente di risolvere il problema 1).
Saluti
Mistral
Corretto errore di battitura, se Mario si riferiva a questo chiedo venia [:I]
quote:
Per parlare di osservatore in termini matematici bisogna definirlo usando le regole della matematica,................................ Per quando riguarda il concetto di tempo, mi pare, ma non ne sono sicuro perchè non ricordo la fonte, che il problema di avere un metodo generale per determinare se un programma si ferma o meno entro un certo tempo t (cioè ad esempio dopo un numero t di passi), è risolubile qualunque sia t finito. Quindi l'osservatore non serve.
Comunque anche la fisica con la meccanica quantistica ha qualche problemino nella definizione dell'osservatore. Il gatto di Schrodinger è vivo o morto?
Grazie per la piacevole chiacchierata, anche se è un po un duetto.
Contrariamente a quanto ti sembra di ricordare in merito ai tempi di arresto della Macchina di T., la dimostrata esistenza di uno stato di "indecidibilità" (Godel) fa sì che esistono proposizioni di cui, a priori, è possibile stabilire la verità o la falsità ed altre in cui non è possibile; si tratta del problema della "indecidibilità". La indecidibilità, riguartdo alla M.di T. consiste nel fatto di non poter a priori sapere se la macchima si fermerà o no, cioè se la macchina svolgerà in un tempo finito o no un algoritmo stabilito dal programma e questa incertezza riduce le questione relative all'intero sistema Osservatore/M.di.T.:
a) A priori l'Osservatore può dimostrare che la macchina si arresterà quindi egli attenderà pazientemente l'esito del computo; (*)
b) Il problema è indecidibile, allora l'Osservatore, in relazione all'importanza della soluzione "investirà" un certo tempo (misurato in scatti della macchina) per verificare se la macchina si arresterà o no.
NOTA (*)
Per fugare dubbi di chi, non addendro al problema della M.diT, e che eventualmente leggesse queste note, l'arresto della macchina corrisponde alla risposta positiva per l'osservatore che, postosi una domanda, egli riceva una risposta di si o di no oppure non ne riceva alcuna; al si o al no la macchina si fermerà, nell'altro caso non si fermerà. In altre parole, se l'osservatore si ponesse la domanda se è possibile calcolare in base al suo programma, con precisione arbitraria, il valore di Pi greco e, se si, procedere al calcolo, la macchina deve prima arrestarsi per dire di essere o no (se non si arrestasse il problema sarebbe indecidibile) in grado di risolvere il calcolo, in caso positivo potrebbe essere programmata per non arrestarsi e passare subito al calcolo dopo aver lasciato sul nastro un messaggio che, si badi bene, l'osservatore deve essere pronto a leggere, per sapere che subito dopo inizia il calcolo del numero irrazionale fino alla precisione voluta. Se l'osservatore ha programmato l'arresto prima del passaggio al calcolo, deve essere lui a riavviare la macchina.
Come si vede, senza osservatore non esisterebbe né la macchina né l'universo e se la macchina esistesse e non si completasse in sistema osservante con l'osservatore, non sarebbe in grado di funzionare.
A proposito della seconda parte della tua citazione sopra riportata, ben dici che la fisica, quella quantistica in particolare, pur avendo, bontà sua, "scoperto" finalmente l'Osservatore, non lo ha definito affatto come si conviene a tutte le entità di un sistema. Quanto alla sfera della matematica, forse neppure ci si è accorti che anche lì è presente il ruolo dell'osservatore, forse perchè non si è ancora ben compreso che la matematica è solo uno stato limite della fisica, essendo essa "la fisica degli oggetti logici" (anziche degli oggetti fisici). Su questo argomento mi sono già dilungato in altri interventi in questo forum.
mario1
quote:
I) il programma della testina è scritto o è comunque noto a chi? All'osservatore, evidentemente!
II) Chi deve stabilire il tempo di osservazione, onde verificare l'eventualità di un arresto dopo del quale raccogliere e valutare l'esito del calcolo? Ancora l'osservatore, evidentemente!
Queste non sono affermazioni matematiche, e con questo non voglio dire che non siano acute.
Per parlare di osservatore in termini matematici bisogna definirlo usando le regole della matematica, se ne fossimo completamente capaci sarebbe un bel passo avanti. Ok! cito di nuovo P.G. Odifreddi, in effetti tra tutti è quello che amo più leggere, mi sembra il più lucido senza troppi fronzoli:
http://www.vialattea.net/odifreddi/treccani.pdf
il link sopra e il contributo che P.G. Odifreddi ha dato alla enciclopedia treccani. Nel paragrafo 5.1 si parla del concetto di "Oracolo" che in un certo senso può essere assimilato almeno a livello "embrionale" al concetto di osservatore interagente, in questo modo si modellizza la variabile "umana" e si danno delle gerarchie di insolubilità. Cioè come dire che si hanno problemi risolubili con uno con due, con n "suggerimenti" di un essere umano, per l'appunto l'oracolo o gli oracoli. Tra l'altro proprio Turing ha introdotto questo concetto.
Per quando riguarda il concetto di tempo, mi pare, ma non ne sono sicuro perchè non ricordo la fonte, che il problema di avere un metodo generale per determinare se un programma si ferma o meno entro un certo tempo t (cioè ad esempio dopo un numero t di passi), è risolubile qualunque sia t finito. Quindi l'osservatore non serve.
Comunque anche la fisica con la meccanica quantistica ha qualche problemino nella definizione dell'osservatore. Il gatto di Schrodinger è vivo o morto? rimane un bel problema a cui esistono molte risposte sensate ma sfortunatamente non equivalenti, anzi la risposta più sensata viene da Bohr : "non ha senso che ti poni la domanda fintanto che non osservi il gatto, e quando l'osservi hai la tua risposta".
Grazie per la piacevole chiacchierata, anche se è un po un duetto.
Mistral
quote:
Originally posted by Mistral
[quote]Originally posted by mariodic
.....
.
1-Problema della Fermata
Dato una macchina di Turing M ed un nastro di input A, esiste un metodo effettivo per determinare se M si fermerà nel caso gli sia dato come input A?
la risposta data da Turing a questo problema è NO.
2-Analogo Logico-Problema della decisione di Hilbert (Entscheidungsproblem):
Data una formula f di un linguaggio del primo ordine (pensate ad esempio a p|ab->p|a v p|b) , e un insieme di formule dette assiomi, esiste un metodo effettivo per determinare se tale formula è dimostrabile dagli assiomi?.
la risposta data da Goedel a questo problema è NO
Questi due problemi/domande sono equivalenti, nel senso che se esiste o non esiste il metodo richiesto in (1), allora, rispettivamente, esiste o non esiste il metodo richiesto in (2), e viceversa.
L'osservatore inteso come essere senziente, in questo caso, non ha alcun ruolo. Filosoficamente ci si può chiedere se è vero che ogni attività umana è almeno in principio computabile nel mondo reale se e solo se è computabile da una macchina di Turing. Questa è grosso modo la tesi di Church e non è un enunciato matematico.
So bene che non esiste modo di determinare a priori se ci sarà l'arresto o no della macchina, quindi questo ideale computer ho si arresta entro un certo tempo fissato dall'osservatore oppure no. So anche che a questo computer non è stato apertamente associato un osservatore. Ed e' proprio da questa mancanza "esplicita" dell'osservatore che prenderei le mosse per una critica "diversa" di questo computer ideale. Ho detto che l'osservatore è mancante solo scientemente ma non lo è sostanzialmente, infatti eccolo dove si annida:
I) il programma della testina è scritto o è comunque noto a chi? All'osservatore, evidentemente!
II) Chi deve stabilire il tempo di osservazione, onde verificare l'eventualità di un arresto dopo del quale raccogliere e valutare l'esito del calcolo? Ancora l'osservatore, evidentemente!
Insomma, ciò che voglio dire è appunto questo: nonostante Turing sia stato attivo fino al 1950 circa, quindi ben più in qua di quando la scienza scoprì l'osservatore quale attore interattivo di ogni esperimento, il mondo matematico, che pur aveva prodotto Godel (con la sua notevole prova) e lo stesso Turing, non riusciva ancora a ravvisare, anche alla matematica, la presenza attiva dell'osservatore.
Il famoso test di Turing, che dimostrava la possibilità logica di decidere se un ipotetico interlocutore, non visibile, era umano o si trattava di un computer interattivo, conferma ancora questa non presa di coscienza, dell'osservatore universale.
Non mi si dica che una cosa è la matematica ed altra e la fisica, perchè la differenza sta solo in questo: la fisica è un rapporto interattivo tra la singolarità limite, che fa capo all'osservatore universale, rispetto agli osservabili "fisici", mentre la matematica è ancora un rapporto interattivo, ma tra la singolarità limite dell'osservatore universale e gli osservabili "logici".
Quanto alla differenza tra i due anzidetti tipi di osservabili, mi sono fin troppo lungamente dilungato in altri interventi in questo forum, massimamente nella sezione denominata "generale" ma, qua e là anche altrove. [:o)]
mario1
quote:
Originally posted by mariodic
.....
Il punto che mi rimane poco chiaro, nonostante le letture sull'argomento, è questo: come fa l'osservatore a capire e, quindi, a sentenziare che il problema è irrisolvibile o indecidibile se egli "non" ha elementi per sapere se il nastro si arresterà in un tempo finito sia pur lunghissimo? Aspettare? E quanto?
Allora, il problema è sostanzialmente questo:
Macchina di Turing (Definizione Intuitiva)
Abbiamo una macchina dotata di un processore e di uno scanner.
Lo scanner può leggere/cancellare/scrivere un nastro su cui le istruzioni sono scritte in celle e sono in numero finito, input iniziale.
La macchina possiede una lista finita di stati in cui può trovarsi. Cosa è fisicamente uno stato è irrilevante, l'importante e che la macchina conosce il suo stato,la definizione dello stato diventa rilevante quando vogliamo realizzare la macchina che abbiamo immaginato.
Data una combinazione di:
-stato corrente
-simbolo segnato sulla cella del nastro in lettura
il processore possiede una lista finita di istruzioni che gli danno la capacità di definire:
-il simbolo da scrivere sulla cella appena letta, cancellando il simbolo esistente.
-muovere lo scanner sulla cella a sinistra o a destra
-stato successivo.
1-Problema della Fermata
Dato una macchina di Turing M ed un nastro di input A, esiste un metodo effettivo per determinare se M si fermerà nel caso gli sia dato come input A?
la risposta data da Turing a questo problema è NO.
2-Analogo Logico-Problema della decisione di Hilbert (Entscheidungsproblem):
Data una formula f di un linguaggio del primo ordine (pensate ad esempio a p|ab->p|a v p|b) , e un insieme di formule dette assiomi, esiste un metodo effettivo per determinare se tale formula è dimostrabile dagli assiomi?.
la risposta data da Goedel a questo problema è NO
Questi due problemi/domande sono equivalenti, nel senso che se esiste o non esiste il metodo richiesto in (1), allora, rispettivamente, esiste o non esiste il metodo richiesto in (2), e viceversa.
L'osservatore inteso come essere senziente, in questo caso, non ha alcun ruolo. Filosoficamente ci si può chiedere se è vero che ogni attività umana è almeno in principio computabile nel mondo reale se e solo se è computabile da una macchina di Turing. Questa è grosso modo la tesi di Church e non è un enunciato matematico.
La domanda filosofica è possiamo costuire macchine reali (quindi serve l'osservatore) che computano funzioni che una macchina di Turing non è in grado di computare?
Saluti
Mistral
quote:
Originally posted by Mistral
Per aiutare l'apertura della discussione cito dall'articolo di P.G. Odifreddi quanto segue:
"Il nome di Turing è oggi famoso soprattutto per la sua analisi del processo di computazione in termini di macchine astratte, dette appunto macchine di Turing. Egli le introdusse per dimostrare che l'attività matematica non è completamente meccanizzabile (ed è quindi impossibile in linea di principio sostituire i matematici con macchine), scoprendo da un lato una macchina (detta universale) che è in grado di svolgere i compiti di qualunque macchina calcolatrice presente o futura (simulandone un programma), e mostrando dall'altro che anche tale macchina ha i suoi limiti. Cosi facendo Turing introdusse la nozione di computer moderno, ed allo stesso tempo ne delimitò i limiti alla potenza teorica.
Il suo contributo è ancora oggi poco capito (al di fuori degli ambienti informatici), ed una delle sue conseguenze è il fatto che non è possibile progettare o costruire computer più potenti di quelli già attualmente in uso: le uniche innovazioni possibili, benché sbandierate come progressi essenziali (ad esempio nello slogan di 'generazione n-sima', con n = 5 attualmente) non sono altro che sviluppi tecnologici relativi a dimensioni o efficienza.
La macchina di Turing fu ottenuta con un esperimento di pensiero analogo a quelli resi famosi dalla fisica moderna, ed in un certo senso è per l'informatica quello che l'equivalenza fra massa ed energia fu per l'energia atomica. In entrambi i casi, benché applicazioni pacifiche e utili siano innegabilmente possibili, è bene ricordare (o, per le anime pure, scoprire) che sono state in realtà quelle militari e distruttive ad averne giustificato e guidato lo sviluppo."
Tra l'altro il piccolo problema che ho proposto nel forum dei "giochi logico matematici e gara" ha molto a che fare con le tecniche meta-matematiche legate al teorema di Goedel.
Saluti
Mistral
Ho dei testi che si soffermano, qualcuno approfonditamente, sulla Macchina di Turing, per esempio: "La mente nuova dell'imperatore"; ad ogni modo ti ringrazio per la informazione sul sito di Odifreddi.
Una domanda è questa:
Considerato che la Macchina di Turing elementare è sinteticamente costituita da un nastro di lunghezza infinita che può spostarsi di un salto alla volta sotto una testina che contiene un programma di lunghezza finita scritto dall'Osservatore, programma che è in grado di decidere, dopo aver letto un input sotto forma binaria proveniente dal nasto che gli passa sotto, di:
a) spostare in un senso o nell'altro il nastro in funzione del bit letto e del programma contenuto nella testina
b) aggiungere, o cancellare, o modificare o non modificare il bit che al momento costituisce l'imput, sempre in funzione del programma
d) arrestare ulteriori movimenti del nastro quando il problema assegnato al programma è stato completato.
Il punto che mi rimane poco chiaro, nonostante le letture sull'argomento, è questo: come fa l'osservatore a capire e, quindi, a sentenziare che il problema è irrisolvibile o indecidibile se egli "non" ha elementi per sapere se il nastro si arresterà in un tempo finito sia pur lunghissimo? Aspettare? E quanto?
mario1
Per aiutare l'apertura della discussione cito dall'articolo di P.G. Odifreddi quanto segue:
"Il nome di Turing è oggi famoso soprattutto per la sua analisi del processo di computazione in termini di macchine astratte, dette appunto macchine di Turing. Egli le introdusse per dimostrare che l'attività matematica non è completamente meccanizzabile (ed è quindi impossibile in linea di principio sostituire i matematici con macchine), scoprendo da un lato una macchina (detta universale) che è in grado di svolgere i compiti di qualunque macchina calcolatrice presente o futura (simulandone un programma), e mostrando dall'altro che anche tale macchina ha i suoi limiti. Cosi facendo Turing introdusse la nozione di computer moderno, ed allo stesso tempo ne delimitò i limiti alla potenza teorica.
Il suo contributo è ancora oggi poco capito (al di fuori degli ambienti informatici), ed una delle sue conseguenze è il fatto che non è possibile progettare o costruire computer più potenti di quelli già attualmente in uso: le uniche innovazioni possibili, benché sbandierate come progressi essenziali (ad esempio nello slogan di 'generazione n-sima', con n = 5 attualmente) non sono altro che sviluppi tecnologici relativi a dimensioni o efficienza.
La macchina di Turing fu ottenuta con un esperimento di pensiero analogo a quelli resi famosi dalla fisica moderna, ed in un certo senso è per l'informatica quello che l'equivalenza fra massa ed energia fu per l'energia atomica. In entrambi i casi, benché applicazioni pacifiche e utili siano innegabilmente possibili, è bene ricordare (o, per le anime pure, scoprire) che sono state in realtà quelle militari e distruttive ad averne giustificato e guidato lo sviluppo."
Il resto lo trovate qui http://www.vialattea.net/odifreddi/bio/turing.htm insieme ad molte altre cose sulla logica matematica e sui teoremi di Goedel e sulle funzioni ricorsive.
Uno dei modi per dimostrare i teoremi di indecidibilità di Goedel e' proprio di usare le macchine di Turing, ha il grosso vantaggio di sembrare in apparenza molto più amichevole di quello che ha usato inizialmente Goedel, che tra parentesi trovate ben illustrato sempre nel sito di PG Odifreddi.
Tra l'altro il piccolo problema che ho proposto nel forum dei "giochi logico matematici e gara" ha molto a che fare con le tecniche meta-matematiche legate al teorema di Goedel.
Saluti
Mistral
Modificato da - mistral il 15/06/2004 00:24:37
Modificato da - mistral il 15/06/2004 00:26:00
"Il nome di Turing è oggi famoso soprattutto per la sua analisi del processo di computazione in termini di macchine astratte, dette appunto macchine di Turing. Egli le introdusse per dimostrare che l'attività matematica non è completamente meccanizzabile (ed è quindi impossibile in linea di principio sostituire i matematici con macchine), scoprendo da un lato una macchina (detta universale) che è in grado di svolgere i compiti di qualunque macchina calcolatrice presente o futura (simulandone un programma), e mostrando dall'altro che anche tale macchina ha i suoi limiti. Cosi facendo Turing introdusse la nozione di computer moderno, ed allo stesso tempo ne delimitò i limiti alla potenza teorica.
Il suo contributo è ancora oggi poco capito (al di fuori degli ambienti informatici), ed una delle sue conseguenze è il fatto che non è possibile progettare o costruire computer più potenti di quelli già attualmente in uso: le uniche innovazioni possibili, benché sbandierate come progressi essenziali (ad esempio nello slogan di 'generazione n-sima', con n = 5 attualmente) non sono altro che sviluppi tecnologici relativi a dimensioni o efficienza.
La macchina di Turing fu ottenuta con un esperimento di pensiero analogo a quelli resi famosi dalla fisica moderna, ed in un certo senso è per l'informatica quello che l'equivalenza fra massa ed energia fu per l'energia atomica. In entrambi i casi, benché applicazioni pacifiche e utili siano innegabilmente possibili, è bene ricordare (o, per le anime pure, scoprire) che sono state in realtà quelle militari e distruttive ad averne giustificato e guidato lo sviluppo."
Il resto lo trovate qui http://www.vialattea.net/odifreddi/bio/turing.htm insieme ad molte altre cose sulla logica matematica e sui teoremi di Goedel e sulle funzioni ricorsive.
Uno dei modi per dimostrare i teoremi di indecidibilità di Goedel e' proprio di usare le macchine di Turing, ha il grosso vantaggio di sembrare in apparenza molto più amichevole di quello che ha usato inizialmente Goedel, che tra parentesi trovate ben illustrato sempre nel sito di PG Odifreddi.
Tra l'altro il piccolo problema che ho proposto nel forum dei "giochi logico matematici e gara" ha molto a che fare con le tecniche meta-matematiche legate al teorema di Goedel.
Saluti
Mistral
Modificato da - mistral il 15/06/2004 00:24:37
Modificato da - mistral il 15/06/2004 00:26:00
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo