ciao a tutti, grazie mille per essere venuti
a questa sessione proprio alla fine del
giorno mi chiamo Tom, vivo a Londra, sono
un informatico e un programmatore a
molti dei colloqui oggi sono stati molto
pratico e pratico e questo discorso è
andando ad essere un po ‘più astratto
e un po ‘più di informatica
Penso che l’ informatica sia
affascinante per se stesso davvero io
significa a parte qualunque sia la pratica
applicazioni di informatica potrebbe
penso che sia super utile
capisci qualcosa su quello che sta succedendo
dentro il computer come quello che è questo
scatola magica che stiamo lavorando con tutti i
giorno e quali sono questi incantesimi che siamo
gettandoci sopra ea volte pensando
su quella roba mi aiuta quando sono
avere una brutta giornata al lavoro e tu sai il mio
i test stanno fallendo o conosci la risorsa
la pipeline non funziona o mai lo sono io
posso tipo di riesco a defluire in questo
mondo un po ‘ più astratto di
pensando all’Informatica e ad esso
solo tipo di aiuta a mantenere la mente
impegnato e mantenere il mio lavoro divertente anche quando
tutto va male così così
su quella nota voglio parlare oggi a
un po ‘sullo sviluppo di un’intuizione
su cosa è possibile fare con
computer cosa possiamo fare con i computer
e più in particolare ciò che non possiamo
fai quello che è impossibile da fare proprio come
se sei un ingegnere è importante
conoscere le leggi della termodinamica
in modo da non spendere il tuo intero
carriera cercando di costruire un perpetuo
macchina da movimento se sei un computer
programma penso sia importante conoscere il
limitazioni di ciò che i computer possono fare
che non passi tutta la tua vita
cercando di convincerli a fare cose simili
loro non possono proprio un mio amico
Recentemente mi ha spiegato che cosa è che
pensa che sia così buono con James Bond
film e ha detto che la cosa migliore
Film di Bond è quello nei primi tre
minuti prima dei titoli di testa
c’è come un film di mini Bond e così via
c’è come il freddo aperto e poi tu
vedere James Bond e lui è un po ‘
infiltrandosi in una struttura nemica e lui
spara a un cattivo ragazzo e
ruba un microfilm e bacia qualcuno
e poi scia giù una montagna e
poi ci sono i titoli di testa e se
ti piacciono davvero i film di Bond
il film mini Bond di tre minuti ottiene
sei davvero entusiasta di vedere il tutto
come il resto del film che sta per
capita e se non ti piacciono i film di Bond
poi in quei primi tre minuti tu
fondamentalmente proprio come avere l’idea che ottieni
tutte le cose buone in un film di James Bond
molto velocemente e poi puoi solo
tipo di zona fuori per tutto il resto di
il film e in realtà non prestare attenzione
e poi alla fine quando la persona tu
è andato strano ti chiede se ti è piaciuto
puoi dire che sì è fantastico davvero
come quel pezzo dove ha sciato il
montagna così sarò cercare di fare questo
parla un po ‘come quello che sto per fare
avere una piccola sequenza pre-credito per
solo darti l’intero messaggio del
parla in una diapositiva e poi puoi semplicemente
cerca di uscire se lo sei, se non lo sei
interessato dopo che quindi questo è il mio tipo
di mini mini talk proprio prima del
crediti di apertura quindi se stai pagando solo
attenzione a una diapositiva si prega di pagare
attenzione a questo è allettante
pensa che possiamo risolvere qualsiasi cosa con
tecnologia e con computer solo da
applicare abbastanza sforzo e abbastanza
ingenuità ma non è questo il caso
sono alcune attività che i programmi non possono
eseguire e alcuni di quei compiti che
i programmi non possono essere molto esoterici
e non sono cose che vorresti
cura direttamente ma ce ne sono altri
cose che i programmi non possono fare come a
conseguenza delle cose esoteriche e
queste altre cose sono molto pratiche
e attinente alle cose che tu ed io
fare nel nostro lavoro di tutti i giorni così è
davvero i programmi non possono fare tutto
esiste una cosa impossibile
programma e poi se questo fosse il Bond
muoverlo sarebbe come la sequenza del titolo ora
è una specie di fine del discorso, quindi se
è tutto quello che ti interessa quindi ora
puoi semplicemente escludere e guardare yeah
grazie, puoi semplicemente retweet violentarmi
sai che la valutazione è molto concisa
parlare dritto al punto, se siete
interessati e volete saperne di più in
un po ‘più in dettaglio, quindi continua ad ascoltare
e sto per spacchettare quella semplice idea
un po ‘e mostrarvi alcuni esempi
di esattamente di cosa sto parlando
quindi per iniziare a mostrarti cosa intendo
qui mi piacerebbe guidarti attraverso come a
il programma può essere impossibile e lo farò
spiegare che ricordandovi di due
fatti della vita due cose sul mondo
che viviamo in ciò che proprio non puoi
cambiare il primo fatto della vita è che noi
esigono collettivamente sistemi universali
ora cosa intendo con un sistema universale
ben Cercherò di spiegare che da
confronto tra due linguaggi di programmazione in modo
per questo esempio, paragone, dico
Python e Ruby e comunque
personalmente come Ruby e questo è quello che io
uso e in questo discorso lo userò come
una sorta di pseudo-codice eseguibile a
spiegare le idee ma le specifiche
il linguaggio di programmazione non ha importanza e
hai il mio permesso di mentalmente
tradurre il codice nelle mie diapositive in
JavaScript o Java o C sharp o
qualunque altra cosa ti sia più comoda
con così dovrebbe, si spera, essere ovvio
a te che possiamo prendere qualsiasi programma
scritto su Python e traducilo
in Ruby è davvero carino
semplice possiamo attraversare a
Tipo di programma Python di una espressione o
dichiarazione alla volta e sostituire ciascuno
piccolo pezzo di sintassi Python con il
pezzo equivalente di sintassi di Ruby e quando
abbiamo finito con quello che abbiamo il
programma originale convertito da Python
in Ruby e possiamo andare nell’altro
direzione anche noi possiamo prendere un rubino
il programma sostituisce ogni pezzo di esso con a
pezzo di Python e quindi finiamo con
un programma Python equivalente quindi in alcuni
senso
Python e Ruby sono esattamente come
potente come l’altro, giusto è possibile
basta prendere un programma scritto in uno di
loro e lo traducono meccanicamente
nell’altra uno e si finisce con un
programma scritto in una lingua diversa
fa esattamente la stessa cosa
tutto ciò che Ruby può fare, Python può fare e
viceversa e questo è bello ma c’è
qualcosa un po ‘ più potente di
bene che è che è possibile
scrivi invece di solo tradurre
singoli programmi Python in Ruby noi
in grado di scrivere un programma speciale che rubino
può fare ciò che qualsiasi programma Python può fare
e ciò che intendo è così che noi
potrebbe scrivere un interprete Python in
questo significa che se hai un
Programma Python e si desidera eseguirlo
tu conosci la mia macchina virtuale Ruby o
qualunque cosa poi non ho bisogno di tradurre
individualmente in un programma rubino rubino
Ho già scritto un programma che rubino
farà quello che fa il programma Python
lo fornite come input per il mio Ruby
implementazione di un interprete Python
e poi il mio programma rubino che ho scritto è
andando a fare qualsiasi cosa sia quel programma Python
dice di fare e di nuovo possiamo farlo il
viceversa pure in modo in entrambe
In quei casi siamo in grado di scrivere solo
questo un programma magico che è una specie di
sufficientemente generico che tu
può alimentarlo un programma scritto in un altro
lingua e sarà solo fare quello che
il programma dice di fare e di nuovo c’è
niente di speciale sull’accoppiamento di
Ruby e Python qui intendo quei due
le lingue sono abbastanza simili ma tu
potrebbe altrettanto bene sapere scrivere a
Interprete Python in JavaScript o tu
potrebbe scrivere un interprete Java Script in
Python, quindi tutte queste lingue
avere un qualche tipo di relazione con
l’un l’altro che è ciò che puoi
implementare gli interpreti l’ uno per l’altro
per uno di loro in uno degli altri
quelli e in realtà c’è un intero
costellazione di sistemi che hanno questo
proprietà che se si sceglie uno qualsiasi dei
questi sistemi è possibile implementarne un altro
sistema in modo da poter implementare a
Interprete JavaScript in Haskell o I
potrebbe implementare un interprete Ruby in
la terra del calcolo non lo consiglio
provi a farlo ma conosci il tutto
di questi sistemi sono una specie di
implementabile l’uno nell’altro e questo è
quel tipo di questo è ciò che intende per
sistemi universali la proprietà di questi
i sistemi sono solitamente chiamati universalità
o anche concorrendo alla completezza così
c’è un gran numero di questi sistemi
e tutti condividono questa proprietà di
universalità e questo è qualcosa che
vogliamo perché i sistemi universali sono
in grado di eseguire software in qualche modo
la loro caratteristica distintiva e in
generale, non vogliamo questa situazione
dove dobbiamo fare individuale
programmi per fare lavori individuali o
macchine individuali per fare individuale
lavori che vogliamo macchine per uso generale
e programmi che non vogliamo ogni volta
vogliamo fare qualcosa di diverso
il negozio e compra una scatola diversa
fa
vogliamo poter comprare una scatola che possa
fare qualsiasi cosa a seconda di ciò che abbiamo inserito
dargli da mangiare e questo è davvero ciò che è
catturato da questa idea di universale
sistemi giusti possiamo dar loro da mangiare programmi
e possono fare cose arbitrarie il
il secondo fatto della vita è che questi
programmi di cui stavo parlando
input che possiamo inserire in Universal
sistemi per convincerli a fare qualsiasi cosa
questi programmi sono essi stessi dati ora
questa sarà una dichiarazione abbastanza ovvia
a chiunque sia un programma per computer e
forse non ho davvero bisogno di decomprimerlo
ma ho intenzione di decomprimere un po ‘
al fine di rendere il mio punto e di nuovo io
utilizzare Ruby come lingua di esempio
qui ma qualsiasi altra lingua lo farà
non c’è niente di speciale in Ruby così
ecco un programma rubino molto semplice
sono io al Ruby un ciclo di stampa eval letto
solo tipo di digitazione in un programma che digito
mette HelloWorld e funziona
stampa ciao mondo e questo è un
programma ma un altro modo di pensare
su quel programma è come alcuni dati I
significa che quello che ho fatto è digitare una serie
di personaggi e quindi in realtà posso digitare
prendi quella serie di personaggi che io
digitato e posso inserirlo solo in a
stringa e così ora ho scritto a
programma diverso che ha ottenuto il mio
programma originale al suo interno come dati e io
non voglio sopra l’uovo, voglio dire che lo è
una cosa abbastanza ovvia che un programma è
solo una serie di personaggi ma il fatto
che puoi prendere un programma e metterlo
all’interno di un altro come un pezzo di dati
potrebbe essere ovvio per noi ma è
le implicazioni sono abbastanza profonde
fuori se guardi questo puoi vederlo
il programma Hello World è davvero solo un
sequenza di caratteri una sequenza di
byte in realtà e dentro la mia programmazione
linguaggio che posso indagare un po ‘
un po ‘potevo letteralmente spacchettarlo
Programma HelloWorld in una serie di
byte che compongono tutti i personaggi
in quel programma e come si guarda a quel
sequenza di byte inizia ad assomigliare
solo un numero binario molto grande che
è quello che è davvero quando un programma
scritto sul disco è davvero giusto
una lunga sequenza di uni e zeri e
qui tu
vedere tutti quelli e zeri e
in realtà se concatenare tutti questi
stringe insieme e li converte in a
numero decimale quindi puoi vedere il
numero decimale che rappresenta questo
programma e questa non è una riduzione di
il programma originale è quello originale
Ciao programma mondiale che lo sta mostrando
tu in un modo leggermente diverso così dentro
un po ‘di senso ciao mondo è il programma Ruby
numero nove sette nove sei e così via ora
se ti ho dato quel numero, allora sì
dato il programma originale che ha
tutte le stesse informazioni del programma
Ho cominciato con ho potuto dare quel
grande numero lungo e poi si potrebbe
decomprimere quel numero nel suo componente
byte e quindi si potrebbe girare ciascuno di
quei byte in un personaggio e girare
li in una stringa e poi si potrebbe
sai valutare quella stringa e tu hai
eseguire il programma originale che ho avviato
con ora alcuni di voi potrebbero aver usato
questo tipo di cosiddetto homo iconico
lingue come alcune delle Lisp
lingue che hanno questo tipo di fantasia
caratteristiche che ti permettono di rappresentare il
sintassi dei programmi nella lingua come
tipo di strutture dati di prima classe
dentro la lingua e loro hanno
operazioni di prima classe nella lingua
che ti permettono di manipolarli e
questa è una caratteristica davvero interessante, ma per a
più o meno grande ogni
il linguaggio di programmazione ha questa caratteristica
ogni programma è in definitiva solo alcuni
dati un grande numero e ogni programmazione
il linguaggio è in grado di manipolarli
cose così sono le lingue homo iconiche
solo quelli che rendono questo
manipolazione di programmi in particolare
facile con una sorta di caratteristiche native che
supportarlo, ma in qualsiasi lingua
puoi manipolare i programmi perché
sono solo numeri e incidentalmente
il fatto che i programmi siano solo numeri
significa che puoi in linea di principio
enumerarli come questo è il programma Ruby
numero nove sette nove e così via, ma tu
potrebbe iniziare solo generando te
conosci il programma numero uno di Ruby e poi
generare il programma Ruby numero due e
quindi generare il programma Ruby numero tre
se continuato ad andare in quel modo si sa
alla fine si genererebbe il prossimo caldo
framework di sviluppo web asincrono
e saresti in grado di acquistare la tua isola
sarebbe brillante
quindi quei due fatti della vita sono in primo luogo
chiediamo questo tipo di programmabile
sistemi universali per uso generale
sono davvero utili e l’altro fatto
della vita sono i programmi che alimentiamo
in queste cose sono solo dati come nessuno
altri dati e quei due fatti della vita
sono gentili nell’aspetto ineludibile
conseguenza che è loop infiniti e
Non sono sicuro che sia ovvio come il
esistenza di loop infiniti necessariamente
segue da quelle due premesse quindi sono
andando a mostrarvi come segue
quindi basta ricapitolare perché ho appena detto ogni
il sistema universale può simulare ogni
altro sistema universale così può farlo Python
simulare Ruby e viceversa e il
fatto che c’è questo tipo di
classe di equivalenza dei sistemi universali
che possono simulare l’un l’altro
che ognuno di questi sistemi può realmente
simulare se stesso è solo uno speciale
caso di qualsiasi sistema universale può
simulare qualcun altro e altro ancora
in particolare ogni programmazione universale
il linguaggio può implementare il proprio
interprete è essenzialmente cosa
universalità significa quindi se tutto ciò che sappiamo
riguardo a Ruby è che è uno di questi
Sistemi universali che non sapevamo
qualcosa sulla sua sintassi o sulla sua
semantica ci hanno appena detto che lo era
Universale che era sicuro e completo
allora questo significa che deve essere possibile
scrivere qualche metodo o funzione o
qualunque cosa tu voglia chiamare in Ruby the
implementa e valuta per Ruby
programmi così qui sto immaginando che questo
valutatore ottiene due argomenti contro il
codice sorgente di un programma e poi esso
ottiene qualche input che quel programma è
andando a leggere sugli ingressi standard ae io
non ho tempo di mostrarti il pieno
implementazione di ciò che questo valuta
il metodo comporterebbe, ma in breve lo farebbe
analizzare il programma in modo che lo avrebbe preso
stringa grande e sarebbe scomposizione
nei suoi pezzi componenti e capire
quale fosse la struttura del programma
e generare una sorta di intermedio
la struttura dei dati è probabilmente un abstract
albero di sintassi e poi valuterà
quel programma e sorta di buffer su il
uscita di quel programma e lo farebbe
valutalo probabilmente camminando
quell’albero sintattico astratto e ogni volta
trova un nodo che rappresenta alcuni
particolare operazione o istruzioni
lo farebbe davvero
operazione o istruzione che manterrebbe
camminando sopra l’albero e poi andando
girare in loop e fare cose fino a quando
era finito e poi sarebbe tornato
l’ output che era stato un po ‘
bufferizzato come stava eseguendo tutto
quelle istruzioni adesso questo è
in realtà abbastanza facile da implementare in a
linguaggio dinamico come Ruby perché Ruby
ha un metodo eval che ti permette
valuta solo una stringa e conosci te
puoi usare la piattaforma su cui ti trovi
su per fare l’analisi e il
valutazione di un programma rubino ma anche se
Ruby non ha questa funzione eval
potrebbe ancora farlo da soli giusto anche
sai che il Ruby stesso è in esecuzione su a
programma per computer scritto probabilmente in C
e potresti semplicemente prendere tutta la logica
da quel programma per computer e ri
implementarlo nella lingua host così per
lingue che non sono state create da eval
in loro puoi sempre andare al
sforzo per implementare che se stessi in modo
una volta che abbiamo questo metodo di valutazione possiamo
usalo per fare essenzialmente domande
sui programmi e la domanda che siamo
chiedere è come sarebbe il risultato di
questo programma essere così posso dire cosa sarebbe
il risultato di questo programma che legge a
stringa dallo standard input e revers
e lo stampa B se l’ho alimentato
string Ciao mondo e valutare sta andando
per rispondere e dire che il risultato sarebbe
essere ciao mondo indietro ora se lo fossimo
in grado di scrivere questo metodo di valutazione che
presumibilmente possiamo perché questo è ciò che
significa che un linguaggio deve essere universale
allora possiamo scrivere un altro metodo chiamato
valutare su se stesso e questo non lo è
qualcosa di speciale questo è solo al posto di
essendo una funzione a due argomenti come
valutare è solo un argomento
e chiama valutare con questo argomento
due volte , questo significa che cosa sta chiedendo
la domanda che cosa ottengo se eseguo questo
programma con il proprio codice sorgente come
input perché i programmi sono solo dati
scrittori puoi sempre farlo così posso
poni la domanda cosa ottengo come risultato
se valuto questo programma con se stesso
come input e quello che torno è bene dentro
questo caso il codice sorgente di quello
programma invertito perché quello che questo
il programma fa è invertire il suo input e se
Sono in grado di scrivere questo quindi posso scrivere
questo programma più ampio che
legge una stringa in un programma in da
input standard e poi si valuta
stesso e guarda quale sia il suo output
e se l’output di quel programma è il
stringa letterale no quindi questo programma
stampa sì altrimenti stampa no così tu
devo focalizzare un po ‘qui per mantenere
traccia di cosa sta succedendo, ma sto andando
chiama questo programma non dice nessun punto RB
e questa è davvero la domanda
di quando corro quando eseguo qualche programma
con se stesso come input , emette no
o non così per esempio posso dire che posso
può riecheggiare in esso questo programma e dire
quando eseguo questo programma da solo
il codice sorgente dice no e in questo
caso la risposta è no non dice no
dice solo il proprio codice sorgente
invertito abbiamo appena visto che mentre se io
dargli questo programma che stampa sappia se
il suo input standard include il letterale
stringa però se nutro la propria fonte
codice come input quindi vedrà che è
il proprio codice sorgente contiene la stringa n
e stamperà no così la risposta a
dice no no sì, niente di quello che ho
ti ha mostrato fino ad ora è particolarmente rischioso
ma il genere DA sorge quando chiediamo cosa
succede se alimentiamo questo programma in
di per sé non è in realtà molto ovvio
cosa succede se si alimenta questo programma
in se stesso quindi passiamo attraverso
così ho il mio dice “nessun punto RB”
e poi ne metto una copia in se stessa
e poi ci sono alcuni possibili
risultati che potrebbero accadere intendo il
due ovvi sono che potrebbe dire
sì o potrebbe dire di no ora se uscite
sì, allora ciò significa che la risposta a
la domanda di questo programma dice di no
quando gli dai il proprio codice sorgente come
l’input è no, non dice no, dice
Sì, quindi la risposta sì non è corretta qui
la risposta che stavamo cercando era no
ma ha detto sì che non è giusto, quindi se
quell’uscita esce allora che significa
il nostro programma non sta facendo quello che è
supposto fare ma esattamente lo stesso
la logica si applica al contrario se
quando alimentiamo questo programma a se stesso il
l’output non è la risposta a farlo
dire no è sì, avrebbe dovuto dire di sì
dovrebbero
No, quindi è anche sbagliato
che il nostro programma è corretto quale
a giudicare da quello che abbiamo visto sul precedente
far scorrere sembrava che fosse tutto corretto
nessuna di queste uscite è accettabile
perché uno di loro sta dando il
risposta sbagliata, cos’altro potrebbe accadere
beh, potrebbe esserci qualche altra uscita
come potrebbe uscire la stringa forse
ma solo guardando il codice sorgente
del programma possiamo vedere che questo è
non è possibile ci sono solo due cose
che potrebbe forse emettere e forse
non è uno di loro, quindi non è giusto
o così l’unica altra opzione qui è
che questo programma non lo finisce mai
mai ti dà una risposta o a
corretto o una risposta errata perché
funziona solo per sempre senza uscita mai
uscendo da esso e nella realtà che è
cosa succede realmente anche se cosa
in realtà accade davvero che è così
manterrà allocare sempre più stack
spazio finché il computer non si esaurisce
memoria e poi tutto si blocca e
si ferma a destra ma quello non è il
colpa del programma sono i computer
caduta e in linea di principio potremmo mantenere
aggiungendo sempre più RAM al computer
e questo programma continuerà a funzionare e
correndo e sarebbe in grado di esaurire
tante risorse quante più ram
e il tempo come siamo stati in grado di fornire ai
potrebbe esaurirli e ancora rompersi
attraverso l’importo che avevamo assegnato a e
questo è davvero ciò che significa per a
programma di funzionare per sempre che può
esaurire tutte le risorse che voi
fornire ad esso l’argomento che ho appena
mostrato che vai come questo rubino è un
linguaggio universale, quindi dobbiamo essere in grado di
scrivi questo metodo o funzione chiamata
valutare in esso, ma se possiamo scrivere quello
valutare il metodo, quindi possiamo costruire a
programma speciale che deve essere riprodotto per sempre
questo dice che nessun punto RB è costruito così
che quando lo si alimenta in sé può farlo
continua a fare loop non c’è altra cosa
che possa farlo sarebbe corretto e
questo argomento non dipende da nessuno
conoscenza di Ruby o Python o
JavaScript o qualsiasi altra lingua tu sia
pensando a te non è necessario conoscere il
sintassi o semantica della lingua
perché ovviamente se conosci la sintassi
di dire Ruby puoi dire che potrei
hanno dimostrato molto di più
semplicemente dicendo te
conoscere
while true do end o qualsiasi altra cosa che è un
ciclo infinito ma puoi solo scrivere
che se sai quali sono le caratteristiche di
la lingua è mentre intendo io Ellis
lo ha definito con un programma concreto ma
l’ argomento sottostante qui è che se
hai questo autointerprete questo
valutare la funzione c’è sempre un modo
di costruire questo programma speciale che
loop per sempre così che ci dà direttamente
o ci dà un modo per venire con un
programma impossibile e lo mostrerò a
tu ora così questi infiniti cicli che sono
parlare di questo è inevitabile
conseguenza della programmazione universale
le lingue sono cattive come loop infiniti dentro
il normale nel codice che scriviamo giorno
al giorno di solito indicano che abbiamo fatto
un qualche tipo di errore, intendo che non lo è
il caso se stai scrivendo a
sistema a lunga durata come un web
server il cui intero lavoro è di sedersi lì
in un ciclo infinito al servizio dell’individuo
richiede ma il codice che scriviamo
giorno per giorno tende a non essere quel tipo di
sistemi di lunga durata come se fossero loro
tendiamo a scrivere piccoli algoritmi
pezzi all’interno di quei sistemi come un HTTP
Richiedi Handler e non vuoi il tuo
gestore di richieste effettive per andare in un file
ciclo infinito perché ciò significa
il cliente non verrà mai servito
quindi se non vogliamo questi loop infiniti
accadere quando non li intendiamo allora
potremmo provare a rimuovere le funzionalità da a
linguaggio di programmazione fino a quando non c’è
modo di causare un ciclo infinito in questo
linguaggio e questo è totalmente fattibile questo
è solo un problema di ingegneria c’è
niente per impedirci di farlo così tu
potrebbe prendere la tua lingua preferita e
inizia a rimuovere le caratteristiche da esso
finché non hai eliminato la possibilità
di avere loop infiniti e solo molto
brevemente che sai che potresti farlo
facendo cose come la rimozione illimitata
iterazioni così potresti permetterti di sapere
si rimuove le cose come while che
solo una sorta di condizione dinamica
che alla fine spererai
diventare pieno in modo da poter dire che stiamo andando
per consentire l’iterazione finita su di voi
conoscere le strutture di dati limitati e le cose
così o tra conoscete le estremità di una
raggio limitato ma non lo lasceremo
basta sedersi in un ciclo arbitrariamente lungo
perché potresti mai smettere di farlo
devo rimuovere la capacità di fare
qualunque sia la causa del tuo linguaggio di programmazione
lambda o chiusure
o funzioni o qualunque cosa siano
prevenire cose come questa è l’ Omega
Combinatore nel calcolo lambda così
tuttavia lo implementeresti nella tua
linguaggio di programmazione che è un a
termine di calcolo lambda che quando tu
valutalo funziona solo per sempre e
mai e poi mai fermarsi, quindi dobbiamo governare
fuori
e questo è in realtà un caso speciale di a
cosa più generale che è che noi
non voglio permettere la funzione ricorsiva
chiama e un modo per impedire che a
modo ingenuo di prevenire esso potrebbe
essere solo per consentire a una funzione di chiamare
un’altra funzione il cui nome viene dopo
nell’alfabeto quindi se ne hai uno
la funzione chiamata a può chiamare una funzione
chiamato B e quindi che può chiamare il
funzione chiamata C ma poi alla fine
sei a corto di funzioni quindi il massimo
la profondità dello stack stack del tuo programma è
limitato dal numero di funzioni in
il tuo programma originale e quello sarà
significa che vuoi anche metterti fuori legge
conosci metaprogramming e dinamico
definizione della funzione e cose del genere
ma va bene possiamo prendere tutti quelli
caratteristiche che non sappiamo permettere
bloccare l’I / O perché non vogliamo essere
in attesa di un morso su una presa di rete
che non arriva mai e così via ci sono a
milioni di altre cose di cui abbiamo bisogno
portare fuori ma puoi sicuramente farlo
quindi abbiamo tolto tutte queste cose al tuo
linguaggio di programmazione preferito vorremmo
finire con qualcosa chiamato un totale
linguaggio di programmazione quindi questo è un
lingua in cui ogni programma è
garantito di finire l’esecuzione perché
hai tirato fuori tutta la lingua
caratteristiche che consentono di sedersi in un
ciclo infinito per sempre ora, se hai
un linguaggio di programmazione totale come quello
chiamiamo quel linguaggio T allora deve
essere impossibile scrivere un interprete
per T nella lingua T ora perché è così
bene, ti ho mostrato perché è perché
se potessimo scrivere un interprete per T
di per sé allora potremmo usare questo tipo di
auto interprete per costruire uno speciale
programma che loop per sempre ma questo
il linguaggio totale che abbiamo costruito non lo fa
ti permettono di scrivere programmi che possono
loop per sempre quindi deve essere impossibile
scrivi questo autointerprete in questo nuovo
linguaggio con cui siamo venuti e
in realtà è davvero controintuitivo
perché interprete per un totale
la lingua è un programma che è garantito
per finire
sai valutare un programma in un totale
il linguaggio è qualcosa che si ferma sempre
alla fine così che si sente esattamente come
il tipo di cosa dovremmo essere in grado di
scrivi in una di queste programmazioni totali
lingue ma non possiamo farlo anche se a
il linguaggio di programmazione totale può esprimere
alcuni programmi che lo finiscono sempre
non posso esprimere tutti i programmi che sempre
Finisci e ti ho mostrato almeno uno
che non può esprimere quale è il suo
interprete ora non è quello che dico
non possiamo scrivere un interprete per questo
linguaggio totale in alcuni altri in alcuni
altro linguaggio che potremmo scrivere
in un linguaggio universale come Ruby o
Python o JavaScript che andrebbe bene
possiamo anche scriverlo in un altro totale
lingua perché poi hai te
sapere se avevamo qualche altra lingua
ti ho chiamato allora potremmo scrivere un
interprete per T in te e anche se tu
usa un linguaggio totale non c’è motivo
perché non abbiamo potuto scrivere l’interprete in
perché è un programma che è
garantito per finire ma non possiamo
scrivi quel linguaggio che programma nel
il linguaggio stesso, quindi tutte queste cose sono
essere gentilmente di natura caritatevole
interessante ma la domanda che
sorprendentemente si presenta come come
questo si collega alla realtà perché
quel linguaggio di programmazione totale che è
aveva un sacco e un sacco di caratteristiche succose
tolto di là non suona davvero
molto simile al tipo di programmazione
lingue che abbiamo effettivamente utilizzare in modo che
valutare la funzione il tipo di sé
il programma interpretativo è impossibile per
qualsiasi lingua totale quindi non c’è totale
linguaggio universale è un tipo
di classi disgiunte di programmazione
lingue ma proprio come totale
i linguaggi di programmazione hanno questo
programma interprete che è impossibile
per loro Universali sistemi universali
Turing completa i linguaggi di programmazione
anche avere programmi impossibili è solo
che sono un po ‘ più difficili
per vedere che quello interprete così
diamo un’occhiata ad alcuni esempi di
alcuni programmi in programmazione universale
lingua ecco un semplice programma in Ruby
questo si legge in una stringa da
input standard e quindi stampa quello
stringa
ora solo guardando questo dovrebbe essere
ovvio che questo programma sempre
Finisce che ho un piccolo asterisco
lì e dice assumendo quello standard
l’input è finito e non bloccante quindi sono
non realmente interessati al programma di
interazioni con il resto del sistema
qui mi interessa solo il comportamento
del programma stesso, supponendolo
sarà sempre in grado di leggere
quella stringa dall’input standard quindi
questo programma finisce sempre guardiamo
in un altro esempio programma questo
legge una stringa dall’input standard
e poi cerca di stamparlo ma
prima che lo stampi , fa questo
mentre vero non fare nulla e semplicemente
guardando che dovrebbe essere ovvio
che quel programma circola sempre per sempre
giusto, colpirò quel loop in
al centro e poi siediti lì
indefinitamente così questi sono specifici
esempi di programmi in questo caso
Ruby e solo guardandoli possiamo
dire se questo programma andrà mai
Finisci o non solo sai solo da
guardandoli ma la domanda è possibile
scriviamo un programma che può decidere questo
in generale per esso per qualsiasi programma così
ciò significa data la fonte di un programma
e il suo contributo possiamo decidere se questo
il programma andrà in loop per sempre o no
e quella domanda è chiamata l’arresto
problema la domanda di te lo sa fare a
il programma finisce mai, diamo un’occhiata
alcuni esempi per vedere se possiamo sviluppare
un’intuizione su quanto sia difficile
il problema è come è un super facile
cosa voglio dire sembra semplice per i due
gli esempi che abbiamo appena visto è piuttosto difficile
come se fossimo nello spettro della difficoltà
questo problema si pone quindi ecco un altro
esempio questo programma finisce sempre
bene questo si legge in una stringa da
input standard e quindi inizializza a
fine variabile alla lunghezza di quello
stringa e poi si siede in un ciclo
concatenando gli asterischi ad alcuni
stringa di output e decrementazione del
contatore e poi quando n punto zero ritorna
vero , stamperà l’ output
quindi questo è essenzialmente un programma
prende una stringa e solo sostituisce tutti
i suoi personaggi con asterischi così poco prima
guardandolo per un minuto dovresti
essere in grado di convincerti che questo
il programma finisce sempre ma la ragione
perché finisce sempre è abbastanza sottile
è la ragione
questo finisce sempre è il quando tu
chiamare leggere sullo standard input sempre
ottenere un oggetto stringa indietro e quando tu
chiama la lunghezza su un oggetto stringa tu
ottieni sempre un numero intero non negativo
e poi quando chiami -1 su a
numero intero non negativo che ottieni sempre
un altro numero intero non negativo e se
lo fai abbastanza volte
alla fine ottenere uno speciale non negativo
intero che quando si chiama lo zero
il metodo su ciò restituirà vero
in modo che il ciclo terminerà sempre e
quindi puoi stamparlo in modo da poterlo fare
rispondere sì in questo caso
conoscenza abbastanza dettagliata del
semantica di tutti questi metodi in
rubini quindi non è così semplice come
guardando il programma che ti serve
capire cosa significano tutte queste cose
e in che modo tutti si sono interrelati sul perché
questo programma finisce sempre coinvolge
tanta conoscenza quindi non è chiaramente un
problema banale perché su esso
implica la comprensione di tutti questi
caratteristiche specifiche di programmazione
linguaggio guardiamo un altro esempio
quindi senza concentrarsi sui dettagli qui
questo è un programma che inizializza a
variabile chiamata n al numero 4 e
quindi si trova all’interno di un anello in cui si trova
controlla se n è la somma di
due numeri primi o meno e se n è il
somma di due numeri primi che incrementa
da 2 e poi continua così
programma sta per verificare se
i numeri pari progressivamente più grandi sono i
somma di due numeri primi o meno, quindi sta andando
per sapere che 4 è 2 più 2 e poi
6 è 3 più 3 e poi 8 è 5 più 3 e
10 è 5 più 5 e 12 è 7 più 5 e così via
continueremo ad andare avanti fino a lì
trova un numero pari che non è la somma
di due numeri primi e poi sta per
fermati e stampa quel numero pari e
quindi la domanda è questo programma
mai finire e la risposta è che non lo facciamo
So che questo programma sta controllando il
congettura di retro oro che è uno dei
una sorta di più antico e più famoso irrisolto
problemi nella teoria dei numeri questo era il primo
congetturato nell’anno 1740 a quello
che tutti i numeri pari sono la somma
di due numeri primi ora questo è stato controllato
empiricamente su un computer per tutto il
numeri pari tra quattro e quattro
quinta
e sono tutti la somma dei due primi
numeri così sembra empiricamente abbastanza
probabilmente questo è vero ma non lo facciamo
avere una prova di ciò e questo significa che
è possibile che se tu lasci questo
il programma funzionava abbastanza a lungo
alla fine trovare un numero pari a quello
non era la somma di due numeri primi e stampa
fuori così sono stati i matematici
cercando di decidere questa domanda in un modo
o l’altro per oltre 250 anni se tu
potrebbe scrivere un programma che potrebbe leggere
questo in e dimmi se stava andando
per finire o no, sarei piuttosto tranquillo
colpito così e questo non vuol dire questo
non puoi farlo solo perché lo è
difficile non significa che non possa essere fatto
ma ora ci stiamo avventurando nel
territorio di essere veramente tranquillo
tu avresti astronomicamente difficile
scrivere un programma che conteneva tutti
moderni teoremi matematici e
conoscenza e dovrebbe anche avere
la capacità di sintetizzare nuovi
teoremi matematici e conoscenza di
quei teoremi esistenti e mantenere
generando sempre più teoremi fino a
ha trovato una prova di un modo o dell’altro
di questo e di quello sta davvero iniziando
il territorio di essere molto molto
difficile da fare e sai che sei
vincendo vincerai il Nobel
Premio se riesci a capire così
questo ora sta iniziando a sembrare molto
difficile problema, ma forse può essere
fatto supponiamo che possa essere fatto
allora questo significa che puoi scrivere a
programma come questo o un metodo come questo
e di nuovo questo è solo il contorno di ciò
ma più o meno quello che farò sarà
è come valutare ma questo è giusto
andando invece di restituire una stringa è
solo andando a restituire vero o falso
e ti dico se un particolare
il programma che avete passato in esso sta andando
per finire o no se è stato eseguito su alcuni
input e in particolare non possiamo solo
eseguire il programma perché questo horts
il metodo deve restituirlo vero o falso
non posso stare lì per sempre parte del
la specificazione di questa cosa è questa
che ti dà sempre una risposta così
questo farà qualcosa un po ‘
un po ‘come valutare che si fermerà
il programma in un albero di sintassi astratto
ma poi piuttosto che correre sul
programma che sta per fare è solo
andando a fare qualche analisi sul programma
e capire se lo farà
alla fine finisci o no e poi lo è
solo andando a restituire vero o falso a
ti dico e ancora questo lo sai
abbastanza ragionevole puoi dire di sapere
questo programma alla fine finisce
stampare
stare in piedi non leggere e poi basta
torna indietro e dì sì, certo che lo è o
si potrebbe dire questo programma
alla fine finirà mentre il vero finirà e
può tornare indietro e dire no, non lo farà e
potresti facilmente scrivere un’implementazione
di questo metodo di cavallo che ottiene questi due
caso giusto intendo che puoi scrivere un
implementazione che risponde correttamente
per ogni insieme finito di programmi perché
puoi semplicemente costruirli nella fonte
codice di cavallo e guardateli
conoscere in un tavolo hash o qualsiasi altra cosa
supponendo che si sa che cosa è la risposta, ma
se potessimo farlo in generale, allora noi
essere in grado di prendere questo metodo di cavallo e
faremo essenzialmente lo stesso
trucco come abbiamo fatto con questo dice no
programma potremmo scrivere un nuovo metodo
chiamato si ferma su se stesso che ti dice
se un programma finisce o meno quando
ha il proprio codice sorgente come input
e quindi possiamo scrivere più a lungo
programma che legge in un programma da
input standard trova che lo usi
ferma il metodo per verificare se questo
il programma finisce sempre quando lo si esegue
il proprio codice sorgente e poi solo
fa il contrario quindi se si ferma su se stesso
ritorna vero e dice sì questo programma
finisce alla fine poi questo è
andando a ciclo per sempre e se ritorna
falso e non dice mai quel programma
si ferma allora questo cadrà
attraverso un’avventura e immediatamente
fermare così ho intenzione di chiamare questo programma
fare l’opposto e Darby come prima della
la domanda importante è che cosa fa questo
programma lo facciamo quando lo eseguiamo da solo
codice sorgente ora prima di guardare a
programma che ha prodotto l’output ma questo
il programma non produce alcun output è
solo andando ad avere uno dei due comportamenti
se prendiamo il suo codice sorgente e alimentiamo
in sé ci sono solo due cose
quello può accadere che può eventualmente alla fine
finire o può loop per sempre ma questo
siamo nella stessa situazione di noi
erano con si dice no Darby
se questo programma alla fine finisce allora
ciò significa che la risposta al
domanda su cosa fa questo programma
quando lo nutri a se stesso è quello
alla fine finisce così quello che dovrebbe
hanno fatto è il contrario dovrebbe avere un
loopato per sempre perché questo programma è
supposto di fare il contrario così
non è il risultato giusto e il
lo stesso argomento si applica nell’altro modo come
bene se lo circonda per sempre allora
avrebbe dovuto fare il contrario
alla fine, quindi è sbagliato
rispondi pure e cosa sta succedendo qui
è che abbiamo progettato un particolare
programma un programma speciale dove nessuno dei due
delle cose che può fare è corretta
comportamento perché è intrinsecamente auto
contraddittoria ora ogni programma che noi
scrivere deve o loop per sempre o
alla fine finisce, ma qualunque sia
quelli che succede in questo caso significa
ciò che ha impedito il metodo era sbagliato
che cosa stava per accadere così da
costruzione di quello che programma quello
abbiamo scritto che abbiamo forzato quella risposta
esce da quel metodo di blocco per essere
sbagliato perché siamo solo sovvertire ciò che
quando ritorna vero per dire che il
il programma alla fine si ferma e continuiamo a farlo
looping e viceversa così a causa di
questo tipo di auto referenzialità siamo noi
in grado di scrivere un programma che fa il
opposto di qualunque cosa si fermi
il controllore dice che lo farà , così abbiamo
sorta di catturato in una trappola crei una
programma che rende impossibile essere
giusto e questo è ciò che l’argomento
sembra che dica se potessimo scrivere
questo blocca il metodo, quindi potremmo usarlo
per costruire uno di questi speciali
programmi che impongono il blocco del metodo
dare la risposta sbagliata in almeno uno
caso, ma se quel metodo di arresto dà il
risposta sbagliata in almeno un caso allora
non è una corretta implementazione di
sale perché una sempre corretta sarebbe sempre
dacci la risposta giusta, così deve essere
impossibile scrivere che fermi il metodo così
a seconda della quantità di quel senso fatta
a te potrebbe essere leggermente pazzesco
o potrebbe essere completamente disinteressato
ma in entrambi i casi ti lascia con
la domanda di chi se ne frega di sapere
questo non è il tipo di cosa che
in realtà ci colpisce nel nostro giorno per giorno
la vita non sembra che non abbiamo mai
in realtà voglio chiedere a un computer di scrivere
un programma che si collegherà per sempre non posso
ricorda l’ ultima volta che qualcuno mi ha chiesto
per farlo, ma spesso vogliamo chiedere
computer altre domande sui programmi
lo sai quando siamo noi quando scriviamo
test che è veramente ci insegnano la
computer per rispondere a domande su
programmi e vogliamo che funzioni così
diciamo che ho appena iniziato a lavorare
per una nuova startup finanziata da VCE nel
valle
il mio capo è venuto da me e ha detto che lui
vuole che scriva un programma che stampa
ciao mondo, ho un mese per farlo
Lo farò, lo sai che facciamo mischia
e cosi ‘so che farai un po’
iterazioni e cose e perché io sono un
responsabile del software artigiano
programmatore non mi sto solo seduto
giù e bash fuori questo programma che
sarebbe ridicolo prima ho intenzione di
scrivere alcuni test e poi una volta che ho
scritto le mie prove, scriverò il mio
implementazione e il test me lo dirà
se la mia implementazione è corretta così
diciamo che per le mie prove lo farò
Scriverò un metodo come questo
questa è una stampa HelloWorld
checker e posso inserire un programma in
questo e sta andando analizzarlo e dire
se quel programma stampi ciao
mondo e io non so voi ma
questo sembra eminentemente ragionevole
sembra il tipo di cosa che è
abbastanza ragionevole essere in grado di chiedere di a
programma quindi se lo implementassi sarei
in grado di dire che questo programma stampa
HelloWorld questo programma che inverte
il suo input se lo alimento come stringa
Ingresso vuol stampa ciao mondo ed è
direi sì, lo sono i tuoi test
passando mentre se lo alimento questo
programma che solo su casi è il suo input e
Lo nutro dello stesso input che restituirà
falso no i tuoi test sono rotti in questo modo
tutto sembra come qualcosa che dovremmo essere
in grado di fare in un mondo giusto ma
Purtroppo, se fosse possibile
scrivi questa stampa ciao world method it
sarebbe anche possibile scrivere questo
ferma il metodo e mi scuso per il
Sintassi di Ruby qui se non ti è familiare
con esso ma essenzialmente quello che sta succedendo
ecco che questo metodo di cavallo costruisce a
programma leggermente più grande da quello
che gli dai il passaggio in un programma
che vuoi sapere se questo
il programma alla fine finisce o no e
quindi costruiamo un po ‘più grande
programma che leggerà
in quel programma da input standard e
quindi valutare quel programma e poi
dopo che il programma è stato valutato, stampa
ciao mondo e mettilo in particolare
valutare qui è solo buttare via qualsiasi
l’output di quel programma è l’ unica cosa
che questo programma HelloWorld può fare è
stampa ciao mondo ma solo dopo il
la valutazione di quel programma è finita
e così una volta che abbiamo costruito questo più grande
programma lo abbiamo passato in quel ciao
checker mondo e poi che ci dirà
se quel programma originale è finito
o no perché quando il programma originale
finisce quindi questo programma più grande stampa
ciao mondo e se il programma originale
si siede in un ciclo infinito per sempre
questo non stampa mai ciao mondo e
questo è chiamato una riduzione di Turing che abbiamo
ridotto il problema dell’arresto al
problema di controllare se un programma
stampa ciao mondo e questo è un po ‘
sospettoso perché questo ci dice che
le stampe ciao problema mondiale non possono
essere più facile del problema dell’arresto
perché puoi usarlo per risolvere lo sai
il problema dell’arresto così dice l’argomento
se possiamo scrivere queste stampe ciao mondo
metodo quindi potremmo usarlo per costruire
una corretta implementazione di quel cavallo
metodo ma abbiamo già visto che lo è
impossibile da attuare correttamente che
metodo del cavallo quindi deve essere impossibile
scrivi che stampa ciao correttore del mondo come
bene e la fonte della difficoltà
ecco che anche se un programma lo fa
contiene il comando print ciao mondo
tu scrivi questo correttore di cui hai bisogno
essere in grado di dire se l’esecuzione di
quel programma lo raggiungerà mai
comando che implica decidere se
la parte del programma prima di quello
il comando finirà mai e basta
dove vive il problema dell’arresto così
è una cattiva notizia vuol dire che non solo lo sono
non in grado di chiedere che molto specifiche
programma fa questo programma mai finire noi
anche non posso chiedere questo programma nemmeno lo fa
cosa voglio che faccia così non puoi chiedere in
generale se un programma incontra il suo
specifica o sai farlo
il programma non contiene bug questo è un
problema che Apple avrebbe amato
essere in grado di prendere tutto il
invio all’App Store e ai feed
li in una macchina magica che
dice loro di sicuro
o se tali comunicazioni stanno chiamando
qualsiasi API privata o se hanno
qualsiasi malware in loro o o qualcosa di simile
quello ma in generale quel tipo di quello
tipo di operazione non è possibile fare
correttamente e questa osservazione è chiamata
Teorema di Rice che dice approssimativamente qualsiasi
interessante proprietà del comportamento del programma
è indecidibile e solo per dirti il
significato di quelle parole la parola
interessante significa che ogni dato programma
può o non può avere quella proprietà così
è qualcosa che vale la pena controllare
comportamento significa in modo specifico
qualcosa sulla funzione che è
calcolato da un programma e questo è un po ‘
vago ma non significa cose come
proprietà sintattiche del programma
ovviamente puoi decidere se a
programmare se il codice sorgente di a
il programma contiene la stringa letterale foo
solo guardandolo ma questi
le proprietà del comportamento del programma sono circa
cosa succede quando il programma esegue un
indecidibile significa che non puoi scrivere a
programma per decidere in generale
quindi questo teorema di Rice è un enorme
downer ma questo è il motivo per cui è un
il programmatore è così fastidioso che non puoi ottenere
il computer per dirti qualcosa
programmi anche se sarebbe davvero
utile per il computer per essere in grado di
ti dico cose sui programmi così
brevemente perché questo accade perché siamo noi
in questa situazione e all’incirca lo è
perché non puoi guardare al futuro
e prevedere ciò che un programma sta per
fare in generale l’unico modo per scoprirlo
di sicuro quello che un programma sta per fare
è di lanciarlo e Stephen Wolfram chiama
questa irriducibilità computazionale
il problema è quando esegui un programma tu
non so in anticipo quanto tempo hai
aspettare che finisca e un po ‘
i programmi non finiranno mai così nessun sistema
che abbastanza potere avuto modo di essere auto
referenziale come questi sistemi universali
non può rispondere correttamente a tutte le domande
di se stesso questo è l’essenziale
contenuto della prima incompletezza della cintura
teorema e tu sai che non era così
scoperto solo nel 1936 ed era a
bomba gigante
e in matematica e continua a
essere una bomba enorme oggi nel computer
scienza che come noi non possiamo non possiamo
costruire questo sistema questi sistemi che sono
in grado di rispondere ad ogni domanda sensata
per rispondere a domande su di sé
sistemi referenziali dobbiamo essere in grado
uscire da loro e usare a
diverso sistema più potente per rispondere
domande sull’autoreferenziale
sistema e che andava bene nel caso di
questi linguaggi di programmazione totali
perché potremmo semplicemente dire oh, semplicemente
uscire da esso e utilizzare un più potente
linguaggio di programmazione per rispondere a questo
domanda ma il problema qui è quello
quando parliamo di Universal
sistemi non esiste un sistema più potente
per noi per l’aggiornamento a questi
i sistemi completi di turing sono i più
potenti sistemi computazionali che noi
sapere come costruire in modo che non possiamo farlo
uscire per rispondere alle domande
abbiamo raggiunto una specie di soffitto di
capacità quindi sono quasi fuori dal tempo che sono
sto solo per provare e partire molto brevemente
tu con le informazioni su come possiamo
far fronte come viviamo in questo
mondo difficile possiamo farcela chiedendo
domande indecidibili ma poi si arrendono
se non riusciamo a trovare una risposta in a
tempo ragionevole quindi se vogliamo fare un
HelloWorld checker potremmo semplicemente eseguire un
programma per 10 secondi e se non è così
stampato HelloWorld entro 10 secondi da noi
può semplicemente arrendersi e dirlo vabbè
non ha stampato HelloWorld e lo faremo
mettilo nel cestino del sapere ma a volte
questo sarà sbagliato perché se tu
Aspettavo un altro secondo forse
l’avrei stampato potrebbe avere
stato uno di quei programmi che stampa
ciao mondo dopo 11 secondi ma se
hai intenzione di aspettare in giro per quelli
allora perché non aspettare 12 secondi o 13
secondi o giù di lì quindi alla fine sei tu
dovrò accettare che tu sia
andando a fare errori
potresti fare molte piccole domande
che collettivamente forniscono prove
la grande domanda che vuoi e questo
è davvero come scrivere test di accettazione
sai che non stai cercando di dimostrare che
un sistema soddisfa le sue specifiche ma tu
prendi solo un mucchio di campioni che danno
Confidate collettivamente che lo faccia
quello che dovrebbe fare potresti chiedere
domande decidibili per essere
conservatore e questo è qualcosa che
ottimizzando i compilatori fanno a
analisi chiamata codice non raggiungibile
eliminazione e per decidere quale
parti di un programma sono attive
che è una proprietà indecidibile di
Teorema di Rice
sopravvalutano solo quali parti del
programma sono raggiungibili
quindi sopravvalutando l’abilità di raggiungere
a volte non riescono a rimuovere pezzi di
codice dal tuo programma che sono in realtà
mai raggiunto nella pratica, ma questo è per
sicurezza che è un compromesso ragionevole e
finalmente potresti decidere di approssimare
un programma trasformandolo in qualcosa
più semplice e poi fare domande su
quella semplice approssimazione si spera
domande decidibili e tipo statico
i sistemi sono un buon esempio di questo
se hai un programma di cui parlare
i valori che conosci x è uguale a 1 y è uguale a x
più 2 potresti trasformarlo in molto
programma più vago sui tipi che potreste dire
x uguale a qualche intero y uguale a x più
qualche intero e rendendolo più vago
hai reso abbastanza probabile che il
domande che volevi chiedere al riguardo e
ora decidibile nel regno di questo tipo
di tipi vaghi e, si spera, se lo hai
progettato correttamente i tuoi tipi che dice
si qualcosa di interessante circa la
programma originale quindi c’è qualche speranza
Va bene, sono fuori tempo se lo sei
interessato a questa roba che ho scritto a
prenota su questa roba non ho tempo
per parlartene , ma io vado
tutto questo tipo di folle folle
teoria delle computazioni, quindi se lo sei
interessato a dare un’occhiata a
che io sappia che non dirò
tutto ciò che è sul computation book
c’è un capitolo gratis se questo ha
ho stuzzicato la tua curiosità grazie davvero
tanto
a questa sessione proprio alla fine del
giorno mi chiamo Tom, vivo a Londra, sono
un informatico e un programmatore a
molti dei colloqui oggi sono stati molto
pratico e pratico e questo discorso è
andando ad essere un po ‘più astratto
e un po ‘più di informatica
Penso che l’ informatica sia
affascinante per se stesso davvero io
significa a parte qualunque sia la pratica
applicazioni di informatica potrebbe
penso che sia super utile
capisci qualcosa su quello che sta succedendo
dentro il computer come quello che è questo
scatola magica che stiamo lavorando con tutti i
giorno e quali sono questi incantesimi che siamo
gettandoci sopra ea volte pensando
su quella roba mi aiuta quando sono
avere una brutta giornata al lavoro e tu sai il mio
i test stanno fallendo o conosci la risorsa
la pipeline non funziona o mai lo sono io
posso tipo di riesco a defluire in questo
mondo un po ‘ più astratto di
pensando all’Informatica e ad esso
solo tipo di aiuta a mantenere la mente
impegnato e mantenere il mio lavoro divertente anche quando
tutto va male così così
su quella nota voglio parlare oggi a
un po ‘sullo sviluppo di un’intuizione
su cosa è possibile fare con
computer cosa possiamo fare con i computer
e più in particolare ciò che non possiamo
fai quello che è impossibile da fare proprio come
se sei un ingegnere è importante
conoscere le leggi della termodinamica
in modo da non spendere il tuo intero
carriera cercando di costruire un perpetuo
macchina da movimento se sei un computer
programma penso sia importante conoscere il
limitazioni di ciò che i computer possono fare
che non passi tutta la tua vita
cercando di convincerli a fare cose simili
loro non possono proprio un mio amico
Recentemente mi ha spiegato che cosa è che
pensa che sia così buono con James Bond
film e ha detto che la cosa migliore
Film di Bond è quello nei primi tre
minuti prima dei titoli di testa
c’è come un film di mini Bond e così via
c’è come il freddo aperto e poi tu
vedere James Bond e lui è un po ‘
infiltrandosi in una struttura nemica e lui
spara a un cattivo ragazzo e
ruba un microfilm e bacia qualcuno
e poi scia giù una montagna e
poi ci sono i titoli di testa e se
ti piacciono davvero i film di Bond
il film mini Bond di tre minuti ottiene
sei davvero entusiasta di vedere il tutto
come il resto del film che sta per
capita e se non ti piacciono i film di Bond
poi in quei primi tre minuti tu
fondamentalmente proprio come avere l’idea che ottieni
tutte le cose buone in un film di James Bond
molto velocemente e poi puoi solo
tipo di zona fuori per tutto il resto di
il film e in realtà non prestare attenzione
e poi alla fine quando la persona tu
è andato strano ti chiede se ti è piaciuto
puoi dire che sì è fantastico davvero
come quel pezzo dove ha sciato il
montagna così sarò cercare di fare questo
parla un po ‘come quello che sto per fare
avere una piccola sequenza pre-credito per
solo darti l’intero messaggio del
parla in una diapositiva e poi puoi semplicemente
cerca di uscire se lo sei, se non lo sei
interessato dopo che quindi questo è il mio tipo
di mini mini talk proprio prima del
crediti di apertura quindi se stai pagando solo
attenzione a una diapositiva si prega di pagare
attenzione a questo è allettante
pensa che possiamo risolvere qualsiasi cosa con
tecnologia e con computer solo da
applicare abbastanza sforzo e abbastanza
ingenuità ma non è questo il caso
sono alcune attività che i programmi non possono
eseguire e alcuni di quei compiti che
i programmi non possono essere molto esoterici
e non sono cose che vorresti
cura direttamente ma ce ne sono altri
cose che i programmi non possono fare come a
conseguenza delle cose esoteriche e
queste altre cose sono molto pratiche
e attinente alle cose che tu ed io
fare nel nostro lavoro di tutti i giorni così è
davvero i programmi non possono fare tutto
esiste una cosa impossibile
programma e poi se questo fosse il Bond
muoverlo sarebbe come la sequenza del titolo ora
è una specie di fine del discorso, quindi se
è tutto quello che ti interessa quindi ora
puoi semplicemente escludere e guardare yeah
grazie, puoi semplicemente retweet violentarmi
sai che la valutazione è molto concisa
parlare dritto al punto, se siete
interessati e volete saperne di più in
un po ‘più in dettaglio, quindi continua ad ascoltare
e sto per spacchettare quella semplice idea
un po ‘e mostrarvi alcuni esempi
di esattamente di cosa sto parlando
quindi per iniziare a mostrarti cosa intendo
qui mi piacerebbe guidarti attraverso come a
il programma può essere impossibile e lo farò
spiegare che ricordandovi di due
fatti della vita due cose sul mondo
che viviamo in ciò che proprio non puoi
cambiare il primo fatto della vita è che noi
esigono collettivamente sistemi universali
ora cosa intendo con un sistema universale
ben Cercherò di spiegare che da
confronto tra due linguaggi di programmazione in modo
per questo esempio, paragone, dico
Python e Ruby e comunque
personalmente come Ruby e questo è quello che io
uso e in questo discorso lo userò come
una sorta di pseudo-codice eseguibile a
spiegare le idee ma le specifiche
il linguaggio di programmazione non ha importanza e
hai il mio permesso di mentalmente
tradurre il codice nelle mie diapositive in
JavaScript o Java o C sharp o
qualunque altra cosa ti sia più comoda
con così dovrebbe, si spera, essere ovvio
a te che possiamo prendere qualsiasi programma
scritto su Python e traducilo
in Ruby è davvero carino
semplice possiamo attraversare a
Tipo di programma Python di una espressione o
dichiarazione alla volta e sostituire ciascuno
piccolo pezzo di sintassi Python con il
pezzo equivalente di sintassi di Ruby e quando
abbiamo finito con quello che abbiamo il
programma originale convertito da Python
in Ruby e possiamo andare nell’altro
direzione anche noi possiamo prendere un rubino
il programma sostituisce ogni pezzo di esso con a
pezzo di Python e quindi finiamo con
un programma Python equivalente quindi in alcuni
senso
Python e Ruby sono esattamente come
potente come l’altro, giusto è possibile
basta prendere un programma scritto in uno di
loro e lo traducono meccanicamente
nell’altra uno e si finisce con un
programma scritto in una lingua diversa
fa esattamente la stessa cosa
tutto ciò che Ruby può fare, Python può fare e
viceversa e questo è bello ma c’è
qualcosa un po ‘ più potente di
bene che è che è possibile
scrivi invece di solo tradurre
singoli programmi Python in Ruby noi
in grado di scrivere un programma speciale che rubino
può fare ciò che qualsiasi programma Python può fare
e ciò che intendo è così che noi
potrebbe scrivere un interprete Python in
questo significa che se hai un
Programma Python e si desidera eseguirlo
tu conosci la mia macchina virtuale Ruby o
qualunque cosa poi non ho bisogno di tradurre
individualmente in un programma rubino rubino
Ho già scritto un programma che rubino
farà quello che fa il programma Python
lo fornite come input per il mio Ruby
implementazione di un interprete Python
e poi il mio programma rubino che ho scritto è
andando a fare qualsiasi cosa sia quel programma Python
dice di fare e di nuovo possiamo farlo il
viceversa pure in modo in entrambe
In quei casi siamo in grado di scrivere solo
questo un programma magico che è una specie di
sufficientemente generico che tu
può alimentarlo un programma scritto in un altro
lingua e sarà solo fare quello che
il programma dice di fare e di nuovo c’è
niente di speciale sull’accoppiamento di
Ruby e Python qui intendo quei due
le lingue sono abbastanza simili ma tu
potrebbe altrettanto bene sapere scrivere a
Interprete Python in JavaScript o tu
potrebbe scrivere un interprete Java Script in
Python, quindi tutte queste lingue
avere un qualche tipo di relazione con
l’un l’altro che è ciò che puoi
implementare gli interpreti l’ uno per l’altro
per uno di loro in uno degli altri
quelli e in realtà c’è un intero
costellazione di sistemi che hanno questo
proprietà che se si sceglie uno qualsiasi dei
questi sistemi è possibile implementarne un altro
sistema in modo da poter implementare a
Interprete JavaScript in Haskell o I
potrebbe implementare un interprete Ruby in
la terra del calcolo non lo consiglio
provi a farlo ma conosci il tutto
di questi sistemi sono una specie di
implementabile l’uno nell’altro e questo è
quel tipo di questo è ciò che intende per
sistemi universali la proprietà di questi
i sistemi sono solitamente chiamati universalità
o anche concorrendo alla completezza così
c’è un gran numero di questi sistemi
e tutti condividono questa proprietà di
universalità e questo è qualcosa che
vogliamo perché i sistemi universali sono
in grado di eseguire software in qualche modo
la loro caratteristica distintiva e in
generale, non vogliamo questa situazione
dove dobbiamo fare individuale
programmi per fare lavori individuali o
macchine individuali per fare individuale
lavori che vogliamo macchine per uso generale
e programmi che non vogliamo ogni volta
vogliamo fare qualcosa di diverso
il negozio e compra una scatola diversa
fa
vogliamo poter comprare una scatola che possa
fare qualsiasi cosa a seconda di ciò che abbiamo inserito
dargli da mangiare e questo è davvero ciò che è
catturato da questa idea di universale
sistemi giusti possiamo dar loro da mangiare programmi
e possono fare cose arbitrarie il
il secondo fatto della vita è che questi
programmi di cui stavo parlando
input che possiamo inserire in Universal
sistemi per convincerli a fare qualsiasi cosa
questi programmi sono essi stessi dati ora
questa sarà una dichiarazione abbastanza ovvia
a chiunque sia un programma per computer e
forse non ho davvero bisogno di decomprimerlo
ma ho intenzione di decomprimere un po ‘
al fine di rendere il mio punto e di nuovo io
utilizzare Ruby come lingua di esempio
qui ma qualsiasi altra lingua lo farà
non c’è niente di speciale in Ruby così
ecco un programma rubino molto semplice
sono io al Ruby un ciclo di stampa eval letto
solo tipo di digitazione in un programma che digito
mette HelloWorld e funziona
stampa ciao mondo e questo è un
programma ma un altro modo di pensare
su quel programma è come alcuni dati I
significa che quello che ho fatto è digitare una serie
di personaggi e quindi in realtà posso digitare
prendi quella serie di personaggi che io
digitato e posso inserirlo solo in a
stringa e così ora ho scritto a
programma diverso che ha ottenuto il mio
programma originale al suo interno come dati e io
non voglio sopra l’uovo, voglio dire che lo è
una cosa abbastanza ovvia che un programma è
solo una serie di personaggi ma il fatto
che puoi prendere un programma e metterlo
all’interno di un altro come un pezzo di dati
potrebbe essere ovvio per noi ma è
le implicazioni sono abbastanza profonde
fuori se guardi questo puoi vederlo
il programma Hello World è davvero solo un
sequenza di caratteri una sequenza di
byte in realtà e dentro la mia programmazione
linguaggio che posso indagare un po ‘
un po ‘potevo letteralmente spacchettarlo
Programma HelloWorld in una serie di
byte che compongono tutti i personaggi
in quel programma e come si guarda a quel
sequenza di byte inizia ad assomigliare
solo un numero binario molto grande che
è quello che è davvero quando un programma
scritto sul disco è davvero giusto
una lunga sequenza di uni e zeri e
qui tu
vedere tutti quelli e zeri e
in realtà se concatenare tutti questi
stringe insieme e li converte in a
numero decimale quindi puoi vedere il
numero decimale che rappresenta questo
programma e questa non è una riduzione di
il programma originale è quello originale
Ciao programma mondiale che lo sta mostrando
tu in un modo leggermente diverso così dentro
un po ‘di senso ciao mondo è il programma Ruby
numero nove sette nove sei e così via ora
se ti ho dato quel numero, allora sì
dato il programma originale che ha
tutte le stesse informazioni del programma
Ho cominciato con ho potuto dare quel
grande numero lungo e poi si potrebbe
decomprimere quel numero nel suo componente
byte e quindi si potrebbe girare ciascuno di
quei byte in un personaggio e girare
li in una stringa e poi si potrebbe
sai valutare quella stringa e tu hai
eseguire il programma originale che ho avviato
con ora alcuni di voi potrebbero aver usato
questo tipo di cosiddetto homo iconico
lingue come alcune delle Lisp
lingue che hanno questo tipo di fantasia
caratteristiche che ti permettono di rappresentare il
sintassi dei programmi nella lingua come
tipo di strutture dati di prima classe
dentro la lingua e loro hanno
operazioni di prima classe nella lingua
che ti permettono di manipolarli e
questa è una caratteristica davvero interessante, ma per a
più o meno grande ogni
il linguaggio di programmazione ha questa caratteristica
ogni programma è in definitiva solo alcuni
dati un grande numero e ogni programmazione
il linguaggio è in grado di manipolarli
cose così sono le lingue homo iconiche
solo quelli che rendono questo
manipolazione di programmi in particolare
facile con una sorta di caratteristiche native che
supportarlo, ma in qualsiasi lingua
puoi manipolare i programmi perché
sono solo numeri e incidentalmente
il fatto che i programmi siano solo numeri
significa che puoi in linea di principio
enumerarli come questo è il programma Ruby
numero nove sette nove e così via, ma tu
potrebbe iniziare solo generando te
conosci il programma numero uno di Ruby e poi
generare il programma Ruby numero due e
quindi generare il programma Ruby numero tre
se continuato ad andare in quel modo si sa
alla fine si genererebbe il prossimo caldo
framework di sviluppo web asincrono
e saresti in grado di acquistare la tua isola
sarebbe brillante
quindi quei due fatti della vita sono in primo luogo
chiediamo questo tipo di programmabile
sistemi universali per uso generale
sono davvero utili e l’altro fatto
della vita sono i programmi che alimentiamo
in queste cose sono solo dati come nessuno
altri dati e quei due fatti della vita
sono gentili nell’aspetto ineludibile
conseguenza che è loop infiniti e
Non sono sicuro che sia ovvio come il
esistenza di loop infiniti necessariamente
segue da quelle due premesse quindi sono
andando a mostrarvi come segue
quindi basta ricapitolare perché ho appena detto ogni
il sistema universale può simulare ogni
altro sistema universale così può farlo Python
simulare Ruby e viceversa e il
fatto che c’è questo tipo di
classe di equivalenza dei sistemi universali
che possono simulare l’un l’altro
che ognuno di questi sistemi può realmente
simulare se stesso è solo uno speciale
caso di qualsiasi sistema universale può
simulare qualcun altro e altro ancora
in particolare ogni programmazione universale
il linguaggio può implementare il proprio
interprete è essenzialmente cosa
universalità significa quindi se tutto ciò che sappiamo
riguardo a Ruby è che è uno di questi
Sistemi universali che non sapevamo
qualcosa sulla sua sintassi o sulla sua
semantica ci hanno appena detto che lo era
Universale che era sicuro e completo
allora questo significa che deve essere possibile
scrivere qualche metodo o funzione o
qualunque cosa tu voglia chiamare in Ruby the
implementa e valuta per Ruby
programmi così qui sto immaginando che questo
valutatore ottiene due argomenti contro il
codice sorgente di un programma e poi esso
ottiene qualche input che quel programma è
andando a leggere sugli ingressi standard ae io
non ho tempo di mostrarti il pieno
implementazione di ciò che questo valuta
il metodo comporterebbe, ma in breve lo farebbe
analizzare il programma in modo che lo avrebbe preso
stringa grande e sarebbe scomposizione
nei suoi pezzi componenti e capire
quale fosse la struttura del programma
e generare una sorta di intermedio
la struttura dei dati è probabilmente un abstract
albero di sintassi e poi valuterà
quel programma e sorta di buffer su il
uscita di quel programma e lo farebbe
valutalo probabilmente camminando
quell’albero sintattico astratto e ogni volta
trova un nodo che rappresenta alcuni
particolare operazione o istruzioni
lo farebbe davvero
operazione o istruzione che manterrebbe
camminando sopra l’albero e poi andando
girare in loop e fare cose fino a quando
era finito e poi sarebbe tornato
l’ output che era stato un po ‘
bufferizzato come stava eseguendo tutto
quelle istruzioni adesso questo è
in realtà abbastanza facile da implementare in a
linguaggio dinamico come Ruby perché Ruby
ha un metodo eval che ti permette
valuta solo una stringa e conosci te
puoi usare la piattaforma su cui ti trovi
su per fare l’analisi e il
valutazione di un programma rubino ma anche se
Ruby non ha questa funzione eval
potrebbe ancora farlo da soli giusto anche
sai che il Ruby stesso è in esecuzione su a
programma per computer scritto probabilmente in C
e potresti semplicemente prendere tutta la logica
da quel programma per computer e ri
implementarlo nella lingua host così per
lingue che non sono state create da eval
in loro puoi sempre andare al
sforzo per implementare che se stessi in modo
una volta che abbiamo questo metodo di valutazione possiamo
usalo per fare essenzialmente domande
sui programmi e la domanda che siamo
chiedere è come sarebbe il risultato di
questo programma essere così posso dire cosa sarebbe
il risultato di questo programma che legge a
stringa dallo standard input e revers
e lo stampa B se l’ho alimentato
string Ciao mondo e valutare sta andando
per rispondere e dire che il risultato sarebbe
essere ciao mondo indietro ora se lo fossimo
in grado di scrivere questo metodo di valutazione che
presumibilmente possiamo perché questo è ciò che
significa che un linguaggio deve essere universale
allora possiamo scrivere un altro metodo chiamato
valutare su se stesso e questo non lo è
qualcosa di speciale questo è solo al posto di
essendo una funzione a due argomenti come
valutare è solo un argomento
e chiama valutare con questo argomento
due volte , questo significa che cosa sta chiedendo
la domanda che cosa ottengo se eseguo questo
programma con il proprio codice sorgente come
input perché i programmi sono solo dati
scrittori puoi sempre farlo così posso
poni la domanda cosa ottengo come risultato
se valuto questo programma con se stesso
come input e quello che torno è bene dentro
questo caso il codice sorgente di quello
programma invertito perché quello che questo
il programma fa è invertire il suo input e se
Sono in grado di scrivere questo quindi posso scrivere
questo programma più ampio che
legge una stringa in un programma in da
input standard e poi si valuta
stesso e guarda quale sia il suo output
e se l’output di quel programma è il
stringa letterale no quindi questo programma
stampa sì altrimenti stampa no così tu
devo focalizzare un po ‘qui per mantenere
traccia di cosa sta succedendo, ma sto andando
chiama questo programma non dice nessun punto RB
e questa è davvero la domanda
di quando corro quando eseguo qualche programma
con se stesso come input , emette no
o non così per esempio posso dire che posso
può riecheggiare in esso questo programma e dire
quando eseguo questo programma da solo
il codice sorgente dice no e in questo
caso la risposta è no non dice no
dice solo il proprio codice sorgente
invertito abbiamo appena visto che mentre se io
dargli questo programma che stampa sappia se
il suo input standard include il letterale
stringa però se nutro la propria fonte
codice come input quindi vedrà che è
il proprio codice sorgente contiene la stringa n
e stamperà no così la risposta a
dice no no sì, niente di quello che ho
ti ha mostrato fino ad ora è particolarmente rischioso
ma il genere DA sorge quando chiediamo cosa
succede se alimentiamo questo programma in
di per sé non è in realtà molto ovvio
cosa succede se si alimenta questo programma
in se stesso quindi passiamo attraverso
così ho il mio dice “nessun punto RB”
e poi ne metto una copia in se stessa
e poi ci sono alcuni possibili
risultati che potrebbero accadere intendo il
due ovvi sono che potrebbe dire
sì o potrebbe dire di no ora se uscite
sì, allora ciò significa che la risposta a
la domanda di questo programma dice di no
quando gli dai il proprio codice sorgente come
l’input è no, non dice no, dice
Sì, quindi la risposta sì non è corretta qui
la risposta che stavamo cercando era no
ma ha detto sì che non è giusto, quindi se
quell’uscita esce allora che significa
il nostro programma non sta facendo quello che è
supposto fare ma esattamente lo stesso
la logica si applica al contrario se
quando alimentiamo questo programma a se stesso il
l’output non è la risposta a farlo
dire no è sì, avrebbe dovuto dire di sì
dovrebbero
No, quindi è anche sbagliato
che il nostro programma è corretto quale
a giudicare da quello che abbiamo visto sul precedente
far scorrere sembrava che fosse tutto corretto
nessuna di queste uscite è accettabile
perché uno di loro sta dando il
risposta sbagliata, cos’altro potrebbe accadere
beh, potrebbe esserci qualche altra uscita
come potrebbe uscire la stringa forse
ma solo guardando il codice sorgente
del programma possiamo vedere che questo è
non è possibile ci sono solo due cose
che potrebbe forse emettere e forse
non è uno di loro, quindi non è giusto
o così l’unica altra opzione qui è
che questo programma non lo finisce mai
mai ti dà una risposta o a
corretto o una risposta errata perché
funziona solo per sempre senza uscita mai
uscendo da esso e nella realtà che è
cosa succede realmente anche se cosa
in realtà accade davvero che è così
manterrà allocare sempre più stack
spazio finché il computer non si esaurisce
memoria e poi tutto si blocca e
si ferma a destra ma quello non è il
colpa del programma sono i computer
caduta e in linea di principio potremmo mantenere
aggiungendo sempre più RAM al computer
e questo programma continuerà a funzionare e
correndo e sarebbe in grado di esaurire
tante risorse quante più ram
e il tempo come siamo stati in grado di fornire ai
potrebbe esaurirli e ancora rompersi
attraverso l’importo che avevamo assegnato a e
questo è davvero ciò che significa per a
programma di funzionare per sempre che può
esaurire tutte le risorse che voi
fornire ad esso l’argomento che ho appena
mostrato che vai come questo rubino è un
linguaggio universale, quindi dobbiamo essere in grado di
scrivi questo metodo o funzione chiamata
valutare in esso, ma se possiamo scrivere quello
valutare il metodo, quindi possiamo costruire a
programma speciale che deve essere riprodotto per sempre
questo dice che nessun punto RB è costruito così
che quando lo si alimenta in sé può farlo
continua a fare loop non c’è altra cosa
che possa farlo sarebbe corretto e
questo argomento non dipende da nessuno
conoscenza di Ruby o Python o
JavaScript o qualsiasi altra lingua tu sia
pensando a te non è necessario conoscere il
sintassi o semantica della lingua
perché ovviamente se conosci la sintassi
di dire Ruby puoi dire che potrei
hanno dimostrato molto di più
semplicemente dicendo te
conoscere
while true do end o qualsiasi altra cosa che è un
ciclo infinito ma puoi solo scrivere
che se sai quali sono le caratteristiche di
la lingua è mentre intendo io Ellis
lo ha definito con un programma concreto ma
l’ argomento sottostante qui è che se
hai questo autointerprete questo
valutare la funzione c’è sempre un modo
di costruire questo programma speciale che
loop per sempre così che ci dà direttamente
o ci dà un modo per venire con un
programma impossibile e lo mostrerò a
tu ora così questi infiniti cicli che sono
parlare di questo è inevitabile
conseguenza della programmazione universale
le lingue sono cattive come loop infiniti dentro
il normale nel codice che scriviamo giorno
al giorno di solito indicano che abbiamo fatto
un qualche tipo di errore, intendo che non lo è
il caso se stai scrivendo a
sistema a lunga durata come un web
server il cui intero lavoro è di sedersi lì
in un ciclo infinito al servizio dell’individuo
richiede ma il codice che scriviamo
giorno per giorno tende a non essere quel tipo di
sistemi di lunga durata come se fossero loro
tendiamo a scrivere piccoli algoritmi
pezzi all’interno di quei sistemi come un HTTP
Richiedi Handler e non vuoi il tuo
gestore di richieste effettive per andare in un file
ciclo infinito perché ciò significa
il cliente non verrà mai servito
quindi se non vogliamo questi loop infiniti
accadere quando non li intendiamo allora
potremmo provare a rimuovere le funzionalità da a
linguaggio di programmazione fino a quando non c’è
modo di causare un ciclo infinito in questo
linguaggio e questo è totalmente fattibile questo
è solo un problema di ingegneria c’è
niente per impedirci di farlo così tu
potrebbe prendere la tua lingua preferita e
inizia a rimuovere le caratteristiche da esso
finché non hai eliminato la possibilità
di avere loop infiniti e solo molto
brevemente che sai che potresti farlo
facendo cose come la rimozione illimitata
iterazioni così potresti permetterti di sapere
si rimuove le cose come while che
solo una sorta di condizione dinamica
che alla fine spererai
diventare pieno in modo da poter dire che stiamo andando
per consentire l’iterazione finita su di voi
conoscere le strutture di dati limitati e le cose
così o tra conoscete le estremità di una
raggio limitato ma non lo lasceremo
basta sedersi in un ciclo arbitrariamente lungo
perché potresti mai smettere di farlo
devo rimuovere la capacità di fare
qualunque sia la causa del tuo linguaggio di programmazione
lambda o chiusure
o funzioni o qualunque cosa siano
prevenire cose come questa è l’ Omega
Combinatore nel calcolo lambda così
tuttavia lo implementeresti nella tua
linguaggio di programmazione che è un a
termine di calcolo lambda che quando tu
valutalo funziona solo per sempre e
mai e poi mai fermarsi, quindi dobbiamo governare
fuori
e questo è in realtà un caso speciale di a
cosa più generale che è che noi
non voglio permettere la funzione ricorsiva
chiama e un modo per impedire che a
modo ingenuo di prevenire esso potrebbe
essere solo per consentire a una funzione di chiamare
un’altra funzione il cui nome viene dopo
nell’alfabeto quindi se ne hai uno
la funzione chiamata a può chiamare una funzione
chiamato B e quindi che può chiamare il
funzione chiamata C ma poi alla fine
sei a corto di funzioni quindi il massimo
la profondità dello stack stack del tuo programma è
limitato dal numero di funzioni in
il tuo programma originale e quello sarà
significa che vuoi anche metterti fuori legge
conosci metaprogramming e dinamico
definizione della funzione e cose del genere
ma va bene possiamo prendere tutti quelli
caratteristiche che non sappiamo permettere
bloccare l’I / O perché non vogliamo essere
in attesa di un morso su una presa di rete
che non arriva mai e così via ci sono a
milioni di altre cose di cui abbiamo bisogno
portare fuori ma puoi sicuramente farlo
quindi abbiamo tolto tutte queste cose al tuo
linguaggio di programmazione preferito vorremmo
finire con qualcosa chiamato un totale
linguaggio di programmazione quindi questo è un
lingua in cui ogni programma è
garantito di finire l’esecuzione perché
hai tirato fuori tutta la lingua
caratteristiche che consentono di sedersi in un
ciclo infinito per sempre ora, se hai
un linguaggio di programmazione totale come quello
chiamiamo quel linguaggio T allora deve
essere impossibile scrivere un interprete
per T nella lingua T ora perché è così
bene, ti ho mostrato perché è perché
se potessimo scrivere un interprete per T
di per sé allora potremmo usare questo tipo di
auto interprete per costruire uno speciale
programma che loop per sempre ma questo
il linguaggio totale che abbiamo costruito non lo fa
ti permettono di scrivere programmi che possono
loop per sempre quindi deve essere impossibile
scrivi questo autointerprete in questo nuovo
linguaggio con cui siamo venuti e
in realtà è davvero controintuitivo
perché interprete per un totale
la lingua è un programma che è garantito
per finire
sai valutare un programma in un totale
il linguaggio è qualcosa che si ferma sempre
alla fine così che si sente esattamente come
il tipo di cosa dovremmo essere in grado di
scrivi in una di queste programmazioni totali
lingue ma non possiamo farlo anche se a
il linguaggio di programmazione totale può esprimere
alcuni programmi che lo finiscono sempre
non posso esprimere tutti i programmi che sempre
Finisci e ti ho mostrato almeno uno
che non può esprimere quale è il suo
interprete ora non è quello che dico
non possiamo scrivere un interprete per questo
linguaggio totale in alcuni altri in alcuni
altro linguaggio che potremmo scrivere
in un linguaggio universale come Ruby o
Python o JavaScript che andrebbe bene
possiamo anche scriverlo in un altro totale
lingua perché poi hai te
sapere se avevamo qualche altra lingua
ti ho chiamato allora potremmo scrivere un
interprete per T in te e anche se tu
usa un linguaggio totale non c’è motivo
perché non abbiamo potuto scrivere l’interprete in
perché è un programma che è
garantito per finire ma non possiamo
scrivi quel linguaggio che programma nel
il linguaggio stesso, quindi tutte queste cose sono
essere gentilmente di natura caritatevole
interessante ma la domanda che
sorprendentemente si presenta come come
questo si collega alla realtà perché
quel linguaggio di programmazione totale che è
aveva un sacco e un sacco di caratteristiche succose
tolto di là non suona davvero
molto simile al tipo di programmazione
lingue che abbiamo effettivamente utilizzare in modo che
valutare la funzione il tipo di sé
il programma interpretativo è impossibile per
qualsiasi lingua totale quindi non c’è totale
linguaggio universale è un tipo
di classi disgiunte di programmazione
lingue ma proprio come totale
i linguaggi di programmazione hanno questo
programma interprete che è impossibile
per loro Universali sistemi universali
Turing completa i linguaggi di programmazione
anche avere programmi impossibili è solo
che sono un po ‘ più difficili
per vedere che quello interprete così
diamo un’occhiata ad alcuni esempi di
alcuni programmi in programmazione universale
lingua ecco un semplice programma in Ruby
questo si legge in una stringa da
input standard e quindi stampa quello
stringa
ora solo guardando questo dovrebbe essere
ovvio che questo programma sempre
Finisce che ho un piccolo asterisco
lì e dice assumendo quello standard
l’input è finito e non bloccante quindi sono
non realmente interessati al programma di
interazioni con il resto del sistema
qui mi interessa solo il comportamento
del programma stesso, supponendolo
sarà sempre in grado di leggere
quella stringa dall’input standard quindi
questo programma finisce sempre guardiamo
in un altro esempio programma questo
legge una stringa dall’input standard
e poi cerca di stamparlo ma
prima che lo stampi , fa questo
mentre vero non fare nulla e semplicemente
guardando che dovrebbe essere ovvio
che quel programma circola sempre per sempre
giusto, colpirò quel loop in
al centro e poi siediti lì
indefinitamente così questi sono specifici
esempi di programmi in questo caso
Ruby e solo guardandoli possiamo
dire se questo programma andrà mai
Finisci o non solo sai solo da
guardandoli ma la domanda è possibile
scriviamo un programma che può decidere questo
in generale per esso per qualsiasi programma così
ciò significa data la fonte di un programma
e il suo contributo possiamo decidere se questo
il programma andrà in loop per sempre o no
e quella domanda è chiamata l’arresto
problema la domanda di te lo sa fare a
il programma finisce mai, diamo un’occhiata
alcuni esempi per vedere se possiamo sviluppare
un’intuizione su quanto sia difficile
il problema è come è un super facile
cosa voglio dire sembra semplice per i due
gli esempi che abbiamo appena visto è piuttosto difficile
come se fossimo nello spettro della difficoltà
questo problema si pone quindi ecco un altro
esempio questo programma finisce sempre
bene questo si legge in una stringa da
input standard e quindi inizializza a
fine variabile alla lunghezza di quello
stringa e poi si siede in un ciclo
concatenando gli asterischi ad alcuni
stringa di output e decrementazione del
contatore e poi quando n punto zero ritorna
vero , stamperà l’ output
quindi questo è essenzialmente un programma
prende una stringa e solo sostituisce tutti
i suoi personaggi con asterischi così poco prima
guardandolo per un minuto dovresti
essere in grado di convincerti che questo
il programma finisce sempre ma la ragione
perché finisce sempre è abbastanza sottile
è la ragione
questo finisce sempre è il quando tu
chiamare leggere sullo standard input sempre
ottenere un oggetto stringa indietro e quando tu
chiama la lunghezza su un oggetto stringa tu
ottieni sempre un numero intero non negativo
e poi quando chiami -1 su a
numero intero non negativo che ottieni sempre
un altro numero intero non negativo e se
lo fai abbastanza volte
alla fine ottenere uno speciale non negativo
intero che quando si chiama lo zero
il metodo su ciò restituirà vero
in modo che il ciclo terminerà sempre e
quindi puoi stamparlo in modo da poterlo fare
rispondere sì in questo caso
conoscenza abbastanza dettagliata del
semantica di tutti questi metodi in
rubini quindi non è così semplice come
guardando il programma che ti serve
capire cosa significano tutte queste cose
e in che modo tutti si sono interrelati sul perché
questo programma finisce sempre coinvolge
tanta conoscenza quindi non è chiaramente un
problema banale perché su esso
implica la comprensione di tutti questi
caratteristiche specifiche di programmazione
linguaggio guardiamo un altro esempio
quindi senza concentrarsi sui dettagli qui
questo è un programma che inizializza a
variabile chiamata n al numero 4 e
quindi si trova all’interno di un anello in cui si trova
controlla se n è la somma di
due numeri primi o meno e se n è il
somma di due numeri primi che incrementa
da 2 e poi continua così
programma sta per verificare se
i numeri pari progressivamente più grandi sono i
somma di due numeri primi o meno, quindi sta andando
per sapere che 4 è 2 più 2 e poi
6 è 3 più 3 e poi 8 è 5 più 3 e
10 è 5 più 5 e 12 è 7 più 5 e così via
continueremo ad andare avanti fino a lì
trova un numero pari che non è la somma
di due numeri primi e poi sta per
fermati e stampa quel numero pari e
quindi la domanda è questo programma
mai finire e la risposta è che non lo facciamo
So che questo programma sta controllando il
congettura di retro oro che è uno dei
una sorta di più antico e più famoso irrisolto
problemi nella teoria dei numeri questo era il primo
congetturato nell’anno 1740 a quello
che tutti i numeri pari sono la somma
di due numeri primi ora questo è stato controllato
empiricamente su un computer per tutto il
numeri pari tra quattro e quattro
quinta
e sono tutti la somma dei due primi
numeri così sembra empiricamente abbastanza
probabilmente questo è vero ma non lo facciamo
avere una prova di ciò e questo significa che
è possibile che se tu lasci questo
il programma funzionava abbastanza a lungo
alla fine trovare un numero pari a quello
non era la somma di due numeri primi e stampa
fuori così sono stati i matematici
cercando di decidere questa domanda in un modo
o l’altro per oltre 250 anni se tu
potrebbe scrivere un programma che potrebbe leggere
questo in e dimmi se stava andando
per finire o no, sarei piuttosto tranquillo
colpito così e questo non vuol dire questo
non puoi farlo solo perché lo è
difficile non significa che non possa essere fatto
ma ora ci stiamo avventurando nel
territorio di essere veramente tranquillo
tu avresti astronomicamente difficile
scrivere un programma che conteneva tutti
moderni teoremi matematici e
conoscenza e dovrebbe anche avere
la capacità di sintetizzare nuovi
teoremi matematici e conoscenza di
quei teoremi esistenti e mantenere
generando sempre più teoremi fino a
ha trovato una prova di un modo o dell’altro
di questo e di quello sta davvero iniziando
il territorio di essere molto molto
difficile da fare e sai che sei
vincendo vincerai il Nobel
Premio se riesci a capire così
questo ora sta iniziando a sembrare molto
difficile problema, ma forse può essere
fatto supponiamo che possa essere fatto
allora questo significa che puoi scrivere a
programma come questo o un metodo come questo
e di nuovo questo è solo il contorno di ciò
ma più o meno quello che farò sarà
è come valutare ma questo è giusto
andando invece di restituire una stringa è
solo andando a restituire vero o falso
e ti dico se un particolare
il programma che avete passato in esso sta andando
per finire o no se è stato eseguito su alcuni
input e in particolare non possiamo solo
eseguire il programma perché questo horts
il metodo deve restituirlo vero o falso
non posso stare lì per sempre parte del
la specificazione di questa cosa è questa
che ti dà sempre una risposta così
questo farà qualcosa un po ‘
un po ‘come valutare che si fermerà
il programma in un albero di sintassi astratto
ma poi piuttosto che correre sul
programma che sta per fare è solo
andando a fare qualche analisi sul programma
e capire se lo farà
alla fine finisci o no e poi lo è
solo andando a restituire vero o falso a
ti dico e ancora questo lo sai
abbastanza ragionevole puoi dire di sapere
questo programma alla fine finisce
stampare
stare in piedi non leggere e poi basta
torna indietro e dì sì, certo che lo è o
si potrebbe dire questo programma
alla fine finirà mentre il vero finirà e
può tornare indietro e dire no, non lo farà e
potresti facilmente scrivere un’implementazione
di questo metodo di cavallo che ottiene questi due
caso giusto intendo che puoi scrivere un
implementazione che risponde correttamente
per ogni insieme finito di programmi perché
puoi semplicemente costruirli nella fonte
codice di cavallo e guardateli
conoscere in un tavolo hash o qualsiasi altra cosa
supponendo che si sa che cosa è la risposta, ma
se potessimo farlo in generale, allora noi
essere in grado di prendere questo metodo di cavallo e
faremo essenzialmente lo stesso
trucco come abbiamo fatto con questo dice no
programma potremmo scrivere un nuovo metodo
chiamato si ferma su se stesso che ti dice
se un programma finisce o meno quando
ha il proprio codice sorgente come input
e quindi possiamo scrivere più a lungo
programma che legge in un programma da
input standard trova che lo usi
ferma il metodo per verificare se questo
il programma finisce sempre quando lo si esegue
il proprio codice sorgente e poi solo
fa il contrario quindi se si ferma su se stesso
ritorna vero e dice sì questo programma
finisce alla fine poi questo è
andando a ciclo per sempre e se ritorna
falso e non dice mai quel programma
si ferma allora questo cadrà
attraverso un’avventura e immediatamente
fermare così ho intenzione di chiamare questo programma
fare l’opposto e Darby come prima della
la domanda importante è che cosa fa questo
programma lo facciamo quando lo eseguiamo da solo
codice sorgente ora prima di guardare a
programma che ha prodotto l’output ma questo
il programma non produce alcun output è
solo andando ad avere uno dei due comportamenti
se prendiamo il suo codice sorgente e alimentiamo
in sé ci sono solo due cose
quello può accadere che può eventualmente alla fine
finire o può loop per sempre ma questo
siamo nella stessa situazione di noi
erano con si dice no Darby
se questo programma alla fine finisce allora
ciò significa che la risposta al
domanda su cosa fa questo programma
quando lo nutri a se stesso è quello
alla fine finisce così quello che dovrebbe
hanno fatto è il contrario dovrebbe avere un
loopato per sempre perché questo programma è
supposto di fare il contrario così
non è il risultato giusto e il
lo stesso argomento si applica nell’altro modo come
bene se lo circonda per sempre allora
avrebbe dovuto fare il contrario
alla fine, quindi è sbagliato
rispondi pure e cosa sta succedendo qui
è che abbiamo progettato un particolare
programma un programma speciale dove nessuno dei due
delle cose che può fare è corretta
comportamento perché è intrinsecamente auto
contraddittoria ora ogni programma che noi
scrivere deve o loop per sempre o
alla fine finisce, ma qualunque sia
quelli che succede in questo caso significa
ciò che ha impedito il metodo era sbagliato
che cosa stava per accadere così da
costruzione di quello che programma quello
abbiamo scritto che abbiamo forzato quella risposta
esce da quel metodo di blocco per essere
sbagliato perché siamo solo sovvertire ciò che
quando ritorna vero per dire che il
il programma alla fine si ferma e continuiamo a farlo
looping e viceversa così a causa di
questo tipo di auto referenzialità siamo noi
in grado di scrivere un programma che fa il
opposto di qualunque cosa si fermi
il controllore dice che lo farà , così abbiamo
sorta di catturato in una trappola crei una
programma che rende impossibile essere
giusto e questo è ciò che l’argomento
sembra che dica se potessimo scrivere
questo blocca il metodo, quindi potremmo usarlo
per costruire uno di questi speciali
programmi che impongono il blocco del metodo
dare la risposta sbagliata in almeno uno
caso, ma se quel metodo di arresto dà il
risposta sbagliata in almeno un caso allora
non è una corretta implementazione di
sale perché una sempre corretta sarebbe sempre
dacci la risposta giusta, così deve essere
impossibile scrivere che fermi il metodo così
a seconda della quantità di quel senso fatta
a te potrebbe essere leggermente pazzesco
o potrebbe essere completamente disinteressato
ma in entrambi i casi ti lascia con
la domanda di chi se ne frega di sapere
questo non è il tipo di cosa che
in realtà ci colpisce nel nostro giorno per giorno
la vita non sembra che non abbiamo mai
in realtà voglio chiedere a un computer di scrivere
un programma che si collegherà per sempre non posso
ricorda l’ ultima volta che qualcuno mi ha chiesto
per farlo, ma spesso vogliamo chiedere
computer altre domande sui programmi
lo sai quando siamo noi quando scriviamo
test che è veramente ci insegnano la
computer per rispondere a domande su
programmi e vogliamo che funzioni così
diciamo che ho appena iniziato a lavorare
per una nuova startup finanziata da VCE nel
valle
il mio capo è venuto da me e ha detto che lui
vuole che scriva un programma che stampa
ciao mondo, ho un mese per farlo
Lo farò, lo sai che facciamo mischia
e cosi ‘so che farai un po’
iterazioni e cose e perché io sono un
responsabile del software artigiano
programmatore non mi sto solo seduto
giù e bash fuori questo programma che
sarebbe ridicolo prima ho intenzione di
scrivere alcuni test e poi una volta che ho
scritto le mie prove, scriverò il mio
implementazione e il test me lo dirà
se la mia implementazione è corretta così
diciamo che per le mie prove lo farò
Scriverò un metodo come questo
questa è una stampa HelloWorld
checker e posso inserire un programma in
questo e sta andando analizzarlo e dire
se quel programma stampi ciao
mondo e io non so voi ma
questo sembra eminentemente ragionevole
sembra il tipo di cosa che è
abbastanza ragionevole essere in grado di chiedere di a
programma quindi se lo implementassi sarei
in grado di dire che questo programma stampa
HelloWorld questo programma che inverte
il suo input se lo alimento come stringa
Ingresso vuol stampa ciao mondo ed è
direi sì, lo sono i tuoi test
passando mentre se lo alimento questo
programma che solo su casi è il suo input e
Lo nutro dello stesso input che restituirà
falso no i tuoi test sono rotti in questo modo
tutto sembra come qualcosa che dovremmo essere
in grado di fare in un mondo giusto ma
Purtroppo, se fosse possibile
scrivi questa stampa ciao world method it
sarebbe anche possibile scrivere questo
ferma il metodo e mi scuso per il
Sintassi di Ruby qui se non ti è familiare
con esso ma essenzialmente quello che sta succedendo
ecco che questo metodo di cavallo costruisce a
programma leggermente più grande da quello
che gli dai il passaggio in un programma
che vuoi sapere se questo
il programma alla fine finisce o no e
quindi costruiamo un po ‘più grande
programma che leggerà
in quel programma da input standard e
quindi valutare quel programma e poi
dopo che il programma è stato valutato, stampa
ciao mondo e mettilo in particolare
valutare qui è solo buttare via qualsiasi
l’output di quel programma è l’ unica cosa
che questo programma HelloWorld può fare è
stampa ciao mondo ma solo dopo il
la valutazione di quel programma è finita
e così una volta che abbiamo costruito questo più grande
programma lo abbiamo passato in quel ciao
checker mondo e poi che ci dirà
se quel programma originale è finito
o no perché quando il programma originale
finisce quindi questo programma più grande stampa
ciao mondo e se il programma originale
si siede in un ciclo infinito per sempre
questo non stampa mai ciao mondo e
questo è chiamato una riduzione di Turing che abbiamo
ridotto il problema dell’arresto al
problema di controllare se un programma
stampa ciao mondo e questo è un po ‘
sospettoso perché questo ci dice che
le stampe ciao problema mondiale non possono
essere più facile del problema dell’arresto
perché puoi usarlo per risolvere lo sai
il problema dell’arresto così dice l’argomento
se possiamo scrivere queste stampe ciao mondo
metodo quindi potremmo usarlo per costruire
una corretta implementazione di quel cavallo
metodo ma abbiamo già visto che lo è
impossibile da attuare correttamente che
metodo del cavallo quindi deve essere impossibile
scrivi che stampa ciao correttore del mondo come
bene e la fonte della difficoltà
ecco che anche se un programma lo fa
contiene il comando print ciao mondo
tu scrivi questo correttore di cui hai bisogno
essere in grado di dire se l’esecuzione di
quel programma lo raggiungerà mai
comando che implica decidere se
la parte del programma prima di quello
il comando finirà mai e basta
dove vive il problema dell’arresto così
è una cattiva notizia vuol dire che non solo lo sono
non in grado di chiedere che molto specifiche
programma fa questo programma mai finire noi
anche non posso chiedere questo programma nemmeno lo fa
cosa voglio che faccia così non puoi chiedere in
generale se un programma incontra il suo
specifica o sai farlo
il programma non contiene bug questo è un
problema che Apple avrebbe amato
essere in grado di prendere tutto il
invio all’App Store e ai feed
li in una macchina magica che
dice loro di sicuro
o se tali comunicazioni stanno chiamando
qualsiasi API privata o se hanno
qualsiasi malware in loro o o qualcosa di simile
quello ma in generale quel tipo di quello
tipo di operazione non è possibile fare
correttamente e questa osservazione è chiamata
Teorema di Rice che dice approssimativamente qualsiasi
interessante proprietà del comportamento del programma
è indecidibile e solo per dirti il
significato di quelle parole la parola
interessante significa che ogni dato programma
può o non può avere quella proprietà così
è qualcosa che vale la pena controllare
comportamento significa in modo specifico
qualcosa sulla funzione che è
calcolato da un programma e questo è un po ‘
vago ma non significa cose come
proprietà sintattiche del programma
ovviamente puoi decidere se a
programmare se il codice sorgente di a
il programma contiene la stringa letterale foo
solo guardandolo ma questi
le proprietà del comportamento del programma sono circa
cosa succede quando il programma esegue un
indecidibile significa che non puoi scrivere a
programma per decidere in generale
quindi questo teorema di Rice è un enorme
downer ma questo è il motivo per cui è un
il programmatore è così fastidioso che non puoi ottenere
il computer per dirti qualcosa
programmi anche se sarebbe davvero
utile per il computer per essere in grado di
ti dico cose sui programmi così
brevemente perché questo accade perché siamo noi
in questa situazione e all’incirca lo è
perché non puoi guardare al futuro
e prevedere ciò che un programma sta per
fare in generale l’unico modo per scoprirlo
di sicuro quello che un programma sta per fare
è di lanciarlo e Stephen Wolfram chiama
questa irriducibilità computazionale
il problema è quando esegui un programma tu
non so in anticipo quanto tempo hai
aspettare che finisca e un po ‘
i programmi non finiranno mai così nessun sistema
che abbastanza potere avuto modo di essere auto
referenziale come questi sistemi universali
non può rispondere correttamente a tutte le domande
di se stesso questo è l’essenziale
contenuto della prima incompletezza della cintura
teorema e tu sai che non era così
scoperto solo nel 1936 ed era a
bomba gigante
e in matematica e continua a
essere una bomba enorme oggi nel computer
scienza che come noi non possiamo non possiamo
costruire questo sistema questi sistemi che sono
in grado di rispondere ad ogni domanda sensata
per rispondere a domande su di sé
sistemi referenziali dobbiamo essere in grado
uscire da loro e usare a
diverso sistema più potente per rispondere
domande sull’autoreferenziale
sistema e che andava bene nel caso di
questi linguaggi di programmazione totali
perché potremmo semplicemente dire oh, semplicemente
uscire da esso e utilizzare un più potente
linguaggio di programmazione per rispondere a questo
domanda ma il problema qui è quello
quando parliamo di Universal
sistemi non esiste un sistema più potente
per noi per l’aggiornamento a questi
i sistemi completi di turing sono i più
potenti sistemi computazionali che noi
sapere come costruire in modo che non possiamo farlo
uscire per rispondere alle domande
abbiamo raggiunto una specie di soffitto di
capacità quindi sono quasi fuori dal tempo che sono
sto solo per provare e partire molto brevemente
tu con le informazioni su come possiamo
far fronte come viviamo in questo
mondo difficile possiamo farcela chiedendo
domande indecidibili ma poi si arrendono
se non riusciamo a trovare una risposta in a
tempo ragionevole quindi se vogliamo fare un
HelloWorld checker potremmo semplicemente eseguire un
programma per 10 secondi e se non è così
stampato HelloWorld entro 10 secondi da noi
può semplicemente arrendersi e dirlo vabbè
non ha stampato HelloWorld e lo faremo
mettilo nel cestino del sapere ma a volte
questo sarà sbagliato perché se tu
Aspettavo un altro secondo forse
l’avrei stampato potrebbe avere
stato uno di quei programmi che stampa
ciao mondo dopo 11 secondi ma se
hai intenzione di aspettare in giro per quelli
allora perché non aspettare 12 secondi o 13
secondi o giù di lì quindi alla fine sei tu
dovrò accettare che tu sia
andando a fare errori
potresti fare molte piccole domande
che collettivamente forniscono prove
la grande domanda che vuoi e questo
è davvero come scrivere test di accettazione
sai che non stai cercando di dimostrare che
un sistema soddisfa le sue specifiche ma tu
prendi solo un mucchio di campioni che danno
Confidate collettivamente che lo faccia
quello che dovrebbe fare potresti chiedere
domande decidibili per essere
conservatore e questo è qualcosa che
ottimizzando i compilatori fanno a
analisi chiamata codice non raggiungibile
eliminazione e per decidere quale
parti di un programma sono attive
che è una proprietà indecidibile di
Teorema di Rice
sopravvalutano solo quali parti del
programma sono raggiungibili
quindi sopravvalutando l’abilità di raggiungere
a volte non riescono a rimuovere pezzi di
codice dal tuo programma che sono in realtà
mai raggiunto nella pratica, ma questo è per
sicurezza che è un compromesso ragionevole e
finalmente potresti decidere di approssimare
un programma trasformandolo in qualcosa
più semplice e poi fare domande su
quella semplice approssimazione si spera
domande decidibili e tipo statico
i sistemi sono un buon esempio di questo
se hai un programma di cui parlare
i valori che conosci x è uguale a 1 y è uguale a x
più 2 potresti trasformarlo in molto
programma più vago sui tipi che potreste dire
x uguale a qualche intero y uguale a x più
qualche intero e rendendolo più vago
hai reso abbastanza probabile che il
domande che volevi chiedere al riguardo e
ora decidibile nel regno di questo tipo
di tipi vaghi e, si spera, se lo hai
progettato correttamente i tuoi tipi che dice
si qualcosa di interessante circa la
programma originale quindi c’è qualche speranza
Va bene, sono fuori tempo se lo sei
interessato a questa roba che ho scritto a
prenota su questa roba non ho tempo
per parlartene , ma io vado
tutto questo tipo di folle folle
teoria delle computazioni, quindi se lo sei
interessato a dare un’occhiata a
che io sappia che non dirò
tutto ciò che è sul computation book
c’è un capitolo gratis se questo ha
ho stuzzicato la tua curiosità grazie davvero
tanto
Please follow and like us: