Più livelli di infinito [chiuso]

Question

Alcuni programmatori non vedo molta rilevanza teorica (CS classi (in particolare i miei studenti).Qui è qualcosa che trovo molto pertinente.Mi permetta di costruire fino a pezzi per coloro che non hanno mai visto prima...

A) problemi di Programmazione può essere riformulato per essere domande sulle lingue.

B) le macchine di Turing riconoscere lingue.

C) le macchine di Turing può essere codificato come (grandi) numeri interi.

D) Pertanto, il numero di macchine di Turing sono countably infinito

E) L'insieme delle parti di un insieme è solo tutti i possibili sottoinsiemi dell'insieme.

F) Se un insieme è countably infinite, la sua potenza è più grande, vale a dire, uncountably infinito.

G) Pertanto, se una lingua è infinito, ha un uncountably infinito numero di sottoinsiemi.Ognuno di questi rappresenta un problema.Ma ci sono solo countably molte macchine di Turing che per risolvere questi problemi.E se non si può risolvere un problema con una macchina di Turing, non può essere risolto.

Conclusione...ci si può solo risolvere un infinitesmally piccola frazione di tutti i problemi.

La mia domanda è quasi qui...

Ogni volta che sono presenti in questo argomento, gli studenti, hanno incastrato sul countably vsuncountably infinito.Che generalmente non hanno forte di matematica sfondi, in modo che i tentativi di spiegare via di diagonalizzazione di Cantor argomento tende a smalto ai loro occhi.

Di solito cerco di dare loro qualcosa, sono in grado di capire, come questo...posto un numero finito di dialogo su qualsiasi parte del conteggio del numero di linea, e siamo in grado di acquisire una quantità finita di quei numeri...ma finita la casella su una parte qualsiasi della linea di numero reale, e siamo in grado di acquisire una quantità infinita di numeri reali.Una sorta di prova che non ci SONO più i numeri reali che ci sono numeri.

Infine la mia domanda...Come SI fa a spiegare il concetto di livelli multipli di infinito a coloro che non hanno mai sentito parlare del concetto, e non può essere matematicamente inclinato?

Modifica Finale:Ho imparato molto da questa domanda e ho apprezzato il feedback.Ho sprecato troppo tempo a cercare di capire cosa "wiki" in realtà era.Ho imparato che c'è un bias insiti in alcune persone, contro la teoria delle domande che mi sento è semplicemente un errore perché molto di ciò che facciamo oggi è stata la teoria di ieri.Ma questo pregiudizio è naturale e mentre io non sono d'accordo con loro sul valore della teoria, non ho alcun problema con esso, e mi aiuta a capire dove i miei studenti sono provenienti da.Penso che il BS commento era inutile.

Io non sento questa domanda è stato un sondaggio o un preditions-per-2009 domanda.Quelli di voi che vogliono solo codificare le domande con la codifica delle risposte potrebbe desiderare di ri-esaminare tale requisito.Io mi sono mosso in questa domanda per le comunità wiki, ma fortemente sentite io sono stato costretto a farlo da un errato uso della forza.

Answer 1

Credo che la tua spiegazione è la più semplice, in quanto questo è ciò che ho imparato. E 'quasi come se i numeri reali hanno molteplici dimensioni di infinito. E 'infinita in una direzione, ma anche in un altro.

Diagonalizzazione è un esperimento molto cool, ma posso vedere come si può andare oltre principianti teste. Ha senso, però, se si dimostra in modo molto deliberata, andando molto lentamente. Basta gettare i numeri veloce può essere difficile da seguire immagino.

Credo che il principio di cardinalità del continuo è anche utile, anche se forse può essere semplificato ad un livello principiante. Dimostrando che non v'è più al di là di semplici interi reali vs. può potenzialmente aiutare qualcosa da 'click'.

Answer 2

Il mio primo passo consigliato per i livelli-di-infinito di insegnamento a persone di limitata sfondo matematico è "Perché i matematici dicono che l'insieme dei numeri pari e l'insieme dei numeri interi sono le stesse dimensioni?" Questo introduce "se è possibile associare ogni membro della serie A con esattamente un membro del gruppo B, i matematici dicono gli insiemi hanno la stessa dimensione." Successiva risulti che ogni frazione (ogni numero razionale) può essere associato ad esattamente un numero di conteggio, utilizzando il metodo diagonale. Una volta che sono soddisfatto di questo, mi far apparire π, che tutti sanno ha un numero infinito di mezzi non multipli cifre nella sua espressione decimale, il che significa che non può essere espresso come una frazione, in modo che vi resteranno, e che che l'insieme di numeri irrazionali è maggiore del set di numeri di conteggio. Alcuni Wiseguys obietteranno che π ha un numero finito di cifre, se si lavora in π di base, vale a dire 1 _π , ma si può tornare a loro con "okay, Brainiac, annotare il numero di giorni in una settimana in π base ".

Answer 3

Dove è la parte "molto rilevante"?

Modifica:. OK, ho scritto il codice professionalmente per 13 anni e non mi chiamare i livelli di infinito rilevante per qualsiasi cosa io abbia mai lavorato

E immagino vorrei richiamare una conclusione diversa dalla teoria. Come è "possiamo risolvere solo infinitamente piccola frazione di tutti i problemi" il limite del nostro mestiere?

Sembra a me come ci sono un infinito (numerabile o non numerabile non sembra fare una differenza) serie di problemi. Pertanto il nostro mestiere è illimitato -. Ci sarà mai a corto di problemi da risolvere

Answer 4

Ci sono diverse decine di migliaia di parole in lingua inglese. È possibile contare il numero di parole in un libro o il numero di libri presenti nell'universo. Non si può contare il numero di libri che sarà mai

Answer 5

Perdona il male è scritto metafore di seguito.

Io personalmente penso di countability/uncountability dicotomia come strettamente legato allo Zeno paradosso della freccia.

L'insieme di tutti i numeri naturali ' e numerabile, c'è un metodo specifico di generare il "prossimo" numero intero, e un passo in avanti.Numerabile di insiemi di muoversi in avanti in questo senso.È quasi come se fosse un velocità, mantiene in movimento in avanti.

---

L'insieme di tutti i numeri reali è numerabile, come zeno freccia.

Se è necessario spostare tra l'origine (0) e la destinazione (1 == 2^-0), si deve prima passare attraverso il punto medio (1/2 == 2^-1).

Ora la vostra destinazione è 1/2;Se si deve andare poi tra l'origine (0) e (1/2), si deve passare attraverso il punto medio (1/4 == 2^-2)

Così via e così via, in modo da ottenere tra 0 e 1, è necessario prima ottenere tra qualcosa in mezzo, che si deve prima ottenere tra qualcosa nel mezzo.Non c'è nulla di finito metodo di calcolo del "prossimo" passo, in modo che il velocità (in contrasto con la velocità dei numeri naturali) in realtà non esiste, il passo successivo non è andando a prendere ovunque.

Edit:

Mi rendo conto ora che questo, probabilmente, ha a che fare con l'ordinamento totale e la mappatura dell'insieme dei numeri naturali per ogni insieme numerabile di insiemi. Se non è possibile totalmente ordinare gli elementi in un insieme, o non è possibile creare un metodo per determinare l'elemento successivo in un set, le probabilità sono esso è incalcolabile.

Answer 6

  

G) Pertanto, se una lingua è infinita, ha un numero infinito di numerabile sottoinsiemi. Ognuno di questi rappresenta un problema.

Visto necessario. Non si può semplicemente assumere che qualsiasi (possibilmente infinito) di macchine di Turing rappresenta necessariamente un 'problema' distinti. Per lo meno, è necessario (a parte) formalizzare la definizione di 'problema' tanto quanto le macchine di Turing sono state formalizzate.

Answer 7

I programmatori (o almeno, il sottoscritto) non hanno spesso a preoccuparsi molto di infinito in questo modo. Quando si inserisce una scatola finita su qualsiasi parte del -macchina rappresentabile numero reale linea , si ottiene un finito quantità di numeri reali. =)

Per esempio, un doppia precisione variabile ha un numero finito di valori possibili: 2 ^ 64.

Answer 8

Ecco un esempio di un problema computabile: all'inizio di una partita a scacchi, è possibile per bianco forzare una vittoria

Il numero di possibili mosse e contromosse è finito. Tutto ciò che dobbiamo fare è costruire alberi e li potare. Non abbiamo ancora fatto solo perché con la tecnologia attuale ci vorrebbero miliardi di anni.

Ecco un esempio di un problema che non è calcolabile:. Data una vista bidimensionale di una scena, costruire un intero modello tridimensionale della scena

Lo facciamo per tutto il tempo. (Fare una stanza con uno spioncino sulla porta. Avere qualcuno arredarla. Guardare attraverso il foro e descrivere tutto quello che vedi.)

Non calcoliamo l'incomputable. Produciamo un risultato approssimativo (proprio come calcoliamo e utilizzare un valore approssimativo di pi greco, un altro numero incomputable). Manteniamo l'aggiornamento del risultato come ulteriori informazioni è disponibile in. Questo è ciò che le illusioni ottiche sono tutti circa. Quando si guarda l'immagine di "un vaso, o è due facce?" il sistema visivo dice: "E 'un vaso. No. Aspetta. E' due facce. No. Aspetta. E 'un vaso." Lo vedi passare avanti e indietro tra le due interpretazioni.

Solo perché qualcosa non è calcolabile è alcun motivo per non farlo.

Answer 9

  

Conclusione ... possiamo risolvere solo infinitesmally piccola frazione di tutti i problemi.

È necessario essere web designer.