Sistema formale
Ho trovato questo problemino on-line molto carino e didatticamente molto formativo credo, ve lo propongo, suggerisco per chi lo conosce di non dare subito la soluzione levando il piacere di trovarla a chi non la conosce. Ecco il problema:
Un sistema formale e' un insieme di regole che permettono di
operare su alcuni oggetti per produrne altri. Il seguente sistema formale e'stato inventato dal logico americano Emil Post intorno al 1920. Gli oggetti su cui opera sono stringhe di caratteri, composte soltanto dai tre caratteri M,I,U.
Il sistema obbedisce alle seguenti tre regole:
1. Se si possiede una stringa che termina con una I, si puo' aggiungere una U alla fine.
2. Se si possiede una stringa del tipo Mx, allora si puo' costruire anche Mxx.
3. Se si possiede una stringa che contiene III, si puo' costruire una nuova stringa mettendo una U al posto di III.
4. Se all’interno di una delle stringhe c’e' la coppia UU, la si puo' eliminare.
Per esempio, la prima regola dice che se si ha a disposizione la stringa MI, allora si puo' costruire MIU.
La seconda regola dice, per esempio, che da MIU si puo' ottenere MIUIU, che da MUM si puo' ottenere MUMUM, e che da MU si puo' ottenere MUU.
Grazie alla terza regola, a partire da UMIIIMU si puo' ottenere UMUMU; da MIIII si possono ottenere sia MIU che MUI; da IIMII non si puo' costruire niente di nuovo usando questa regola, perche' le tre I devono essere in fila; da MIII si puo' costruire MU. Attenzione: le regole non possono essere usate al contrario: da MU non e' possibile passare a MIII.
Con la quarta regola si puo' passare da UUU a U; da MUUUIII si puo' passare a MUIII.
Queste regole costituiscono il “modo di ragionare” all’interno del sistema formale, mentre le stringhe che si ottengono saranno chiamate “teoremi”.
Analogamente a quanto succede, per esempio, nella geometria euclidea, ogni teorema dipende da teoremi dimostrati precedentemente, i quali a loro volta dipendono da altri teoremi, e cos`ı via fino al punto di partenza, dove si trovano gli assiomi.
Anche in questo sistema formale c’e' un assioma, la stringa MI. A partire da questa stringa (e solo da questa), utilizzando le quattro regole esposte sopra, e' possibile ottenere la stringa MU?
Saluti
Mistral
Un sistema formale e' un insieme di regole che permettono di
operare su alcuni oggetti per produrne altri. Il seguente sistema formale e'stato inventato dal logico americano Emil Post intorno al 1920. Gli oggetti su cui opera sono stringhe di caratteri, composte soltanto dai tre caratteri M,I,U.
Il sistema obbedisce alle seguenti tre regole:
1. Se si possiede una stringa che termina con una I, si puo' aggiungere una U alla fine.
2. Se si possiede una stringa del tipo Mx, allora si puo' costruire anche Mxx.
3. Se si possiede una stringa che contiene III, si puo' costruire una nuova stringa mettendo una U al posto di III.
4. Se all’interno di una delle stringhe c’e' la coppia UU, la si puo' eliminare.
Per esempio, la prima regola dice che se si ha a disposizione la stringa MI, allora si puo' costruire MIU.
La seconda regola dice, per esempio, che da MIU si puo' ottenere MIUIU, che da MUM si puo' ottenere MUMUM, e che da MU si puo' ottenere MUU.
Grazie alla terza regola, a partire da UMIIIMU si puo' ottenere UMUMU; da MIIII si possono ottenere sia MIU che MUI; da IIMII non si puo' costruire niente di nuovo usando questa regola, perche' le tre I devono essere in fila; da MIII si puo' costruire MU. Attenzione: le regole non possono essere usate al contrario: da MU non e' possibile passare a MIII.
Con la quarta regola si puo' passare da UUU a U; da MUUUIII si puo' passare a MUIII.
Queste regole costituiscono il “modo di ragionare” all’interno del sistema formale, mentre le stringhe che si ottengono saranno chiamate “teoremi”.
Analogamente a quanto succede, per esempio, nella geometria euclidea, ogni teorema dipende da teoremi dimostrati precedentemente, i quali a loro volta dipendono da altri teoremi, e cos`ı via fino al punto di partenza, dove si trovano gli assiomi.
Anche in questo sistema formale c’e' un assioma, la stringa MI. A partire da questa stringa (e solo da questa), utilizzando le quattro regole esposte sopra, e' possibile ottenere la stringa MU?
Saluti
Mistral
Risposte
Ciao Mistral.
Il giochino che hai trovato e' stato definito nei primi capitoli del libro di Douglas Hofstadter "Goedel, Escher, Bach" (pubblicato in Italia da Adelphi).
Luigi
Il giochino che hai trovato e' stato definito nei primi capitoli del libro di Douglas Hofstadter "Goedel, Escher, Bach" (pubblicato in Italia da Adelphi).
Luigi
quote:
Originally posted by Cygni_61
Ciao Mistral.
Il giochino che hai trovato e' stato definito nei primi capitoli del libro di Douglas Hofstadter "Goedel, Escher, Bach" (pubblicato in Italia da Adelphi).
Luigi
Caspiterina l'ho pure letto 10 anni fa quel libro e non mi ricordavo neppure, inutile gli anni passano. In realtà io l'ho ritrovato on-line poco tempo fa mi è piaciuto e l'ho proposto dicendo che Post l'aveva inventato negli anni venti...., direi che Post e arrivato prima di Hofstadter che la copiato da Post...
Ma in fondo tutto questo cosa centra con il piacere di risolverlo per conto proprio?
Saluti
Mistral
vediamo un pò che ho combinato!
I)
per ottenere MU da MI occorre necessariamente eliminare tutte le I che vengono via via "creandosi"; ora, le I possono essere eliminate solo attraverso la 3, che le elimina di tre in tre; quindi per ottenere MU è necessario che si abbiano 3k I, per un opportuno k (si osservi che questa condizione non è sufficiente).
II)
A partire da MI, l'unico modo per costruire delle I è utilizzare la 2; l'unica speranza che ho è quindi quella di riuscire ad ottenere 3k I utilizzando ripetutamente la 2; osserviamo ora che la 2 raddoppia sempre tutto quello che trova ne segue che, dopo j volte, si avranno 2^h I, per un opportuno h <= j.
III)
osservato questo, resta da dimostrare che 3 non divide 2^h, per nessun h.
I caso: h pari; allora h = 2n;
ora 2^h = (2^2)^n congruo ad 1 (mod3) dal piccolo teorema di Fermat; ne consegue che 3 non divide 2^h se h è pari.
II caso: h dispari; allora h = 2m + 1;
ora, 2^h = (2^2)^m * 2 congruo a 2 (mod3) dal piccolo teorema di Fermat; ne consegue che 3 non divide 2^h, neanche se h è dispari;
in definitiva, non è possibile ottenere la stringa MU a partire da MI.
fammi sapere, ciao, ubermensch
p.s. comunque bello sto giochetto!
I)
per ottenere MU da MI occorre necessariamente eliminare tutte le I che vengono via via "creandosi"; ora, le I possono essere eliminate solo attraverso la 3, che le elimina di tre in tre; quindi per ottenere MU è necessario che si abbiano 3k I, per un opportuno k (si osservi che questa condizione non è sufficiente).
II)
A partire da MI, l'unico modo per costruire delle I è utilizzare la 2; l'unica speranza che ho è quindi quella di riuscire ad ottenere 3k I utilizzando ripetutamente la 2; osserviamo ora che la 2 raddoppia sempre tutto quello che trova ne segue che, dopo j volte, si avranno 2^h I, per un opportuno h <= j.
III)
osservato questo, resta da dimostrare che 3 non divide 2^h, per nessun h.
I caso: h pari; allora h = 2n;
ora 2^h = (2^2)^n congruo ad 1 (mod3) dal piccolo teorema di Fermat; ne consegue che 3 non divide 2^h se h è pari.
II caso: h dispari; allora h = 2m + 1;
ora, 2^h = (2^2)^m * 2 congruo a 2 (mod3) dal piccolo teorema di Fermat; ne consegue che 3 non divide 2^h, neanche se h è dispari;
in definitiva, non è possibile ottenere la stringa MU a partire da MI.
fammi sapere, ciao, ubermensch
p.s. comunque bello sto giochetto!
mi "autofaccio" una piccola correzione;
ovviamente dopo aver utilizzato alcune volte la 2, potrei utilizzare, per togliere qualche I, la 3 un certo numero di volte s; otterrò, quindi 2^h - 3s I; è ovvio che le congruenze rimangono invariate; così come, iterando nuovamente la 2, diciamo t volte si otterranno (2^h -3s)^t I, anche in questo caso le congruenze rimangono invariate in quanto vale un risultato che dice che se p è primo, allora (a+b)^p è congruo ad a^p + b^p (modp).
procedendo in questo modo quindi il mio ragionamento dovrebbe valere anche mischiando iterazioni della 2 e della 3.
Fammi sapere, ciao, ubermensch
p.s. starò fuori Roma fino a sabato, quindi, eventualmente, non potrò nè rispondere, nè, eventualmente, tentare di correggermi, fino a sabato.
ovviamente dopo aver utilizzato alcune volte la 2, potrei utilizzare, per togliere qualche I, la 3 un certo numero di volte s; otterrò, quindi 2^h - 3s I; è ovvio che le congruenze rimangono invariate; così come, iterando nuovamente la 2, diciamo t volte si otterranno (2^h -3s)^t I, anche in questo caso le congruenze rimangono invariate in quanto vale un risultato che dice che se p è primo, allora (a+b)^p è congruo ad a^p + b^p (modp).
procedendo in questo modo quindi il mio ragionamento dovrebbe valere anche mischiando iterazioni della 2 e della 3.
Fammi sapere, ciao, ubermensch
p.s. starò fuori Roma fino a sabato, quindi, eventualmente, non potrò nè rispondere, nè, eventualmente, tentare di correggermi, fino a sabato.
quote:
Originally posted by ubermensch
mi "autofaccio" una piccola correzione;
ovviamente dopo aver utilizzato alcune volte la 2, potrei utilizzare, per togliere qualche I, la 3 un certo numero di volte s; otterrò, quindi 2^h - 3s I; è ovvio che le congruenze rimangono invariate; così come, iterando nuovamente la 2, diciamo t volte si otterranno (2^h -3s)^t I, anche in questo caso le congruenze rimangono invariate in quanto vale un risultato che dice che se p è primo, allora (a+b)^p è congruo ad a^p + b^p (modp).
procedendo in questo modo quindi il mio ragionamento dovrebbe valere anche mischiando iterazioni della 2 e della 3.
Fammi sapere, ciao, ubermensch
p.s. starò fuori Roma fino a sabato, quindi, eventualmente, non potrò nè rispondere, nè, eventualmente, tentare di correggermi, fino a sabato.
Ok è giusto faccio una sintesi per gli altri lettori del post:
Allora, la somma delle I dell'assioma (MI) è uguale a 1. Le regole 1 e 4 lasciano intatta la somma delle I, dato che agiscono solo sulle U. La regola 3 invece fa diminuire di 3 la somma delle I di una stringa. Però la regola 3 pur cambiando la somma delle I, ma non la fa mai diventare un multiplo di 3 se già prima non lo era. La regola 2 invece raddoppia la somma delle I, e anche questa non crea un multiplo di 3 se non a partire da un altro multiplo di 3 (infatti 2n è multiplo di 3 solo se n lo è ).
In conclusione non si può ottenere MU da MI. Molto carino vero? quindi ho assumo MU come assioma oppure non riesco a dimostrarlo con le regole...insomma un pò quello che succede con il postulato delle parallele nella geometria, o con l'assioma della scelta o l'ipotesi del continuo in teoria degli insiemi.
Saluti
Mistral
io mi ero posto anche un altro problema, a cui però ancora non ho saputo rispondere; consideriamo l'insieme delle stringhe M______ dove i trattini possono essere riempiti o da I o da U; prendiamo come assioma MI e MU; la domanda è: possiamo costruire tutte le stringhe del tipo citato o manca qualche assioma?
se a qualcuno va di pensarci...
ciao, ubermensch
se a qualcuno va di pensarci...
ciao, ubermensch
quote:
Originally posted by ubermensch
io mi ero posto anche un altro problema, a cui però ancora non ho saputo rispondere; consideriamo l'insieme delle stringhe M______ dove i trattini possono essere riempiti o da I o da U; prendiamo come assioma MI e MU; la domanda è: possiamo costruire tutte le stringhe del tipo citato o manca qualche assioma?
se a qualcuno va di pensarci...
ciao, ubermensch
ok ci penso [:)]
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo