Estremamente probabile, questo esempio concreto è inutile. Quindi è qualsiasi altro esempio concreto. Tuttavia, ci sono molti di questi esempi e non sappiamo quale manciata sarà utile.

Alcuni antichi sprecavano tempo in ricerche sulla teoria dei numeri, alcuni dei quali finirono per essere praticamente utili. Alcuni hanno studiato il movimento delle stelle in dettaglio superando di gran lunga le esigenze di calendario e di navigazione. Anche questo si è rivelato utile.

Anche molti, molti studi hanno portato a vicoli ciechi. A quel tempo, non si poteva dire quale di loro l'avrebbe fatto.

La funzione busy beaver è un importante artefatto della teoria della computabilità, in particolare è nota per crescere (asintoticamente) più velocemente di qualsiasi funzione calcolabile. Intuitivamente questo significa che è una sequenza "più difficile" da calcolare rispetto a tutte le sequenze calcolabili.

Quindi, dà origine a un nuovo tipo di dimostrazione per esaurimento. Supponiamo di dover scrivere un programma della macchina di Turing P per testare tutti i possibili casi speciali di una dimostrazione (potenzialmente un numero infinito di casi). Se il programma trova un problema con la prova, si fermerà. Altrimenti, funzionerà per sempre. Secondo la definizione di macchina castoro occupata, se la macchina di Turing P si ferma, si fermerà prima della macchina castoro occupata con il numero equivalente di stati . Quindi, tutto quello che dobbiamo fare per dimostrare la nostra teorema è quello di eseguire il nostro programma per il numero di passi specificato, e se non fermare prima che la nostra macchina castoro occupato poi abbiamo la garanzia che non sarà mai fermata, e in effetti non ci può non contraddizioni di casi speciali alla nostra dimostrazione.

L'uso di questo fatto non è fattibile sull'attuale hardware del computer, ma raramente è stato un ostacolo a questo tipo di ricerca. Se il nostro concetto di hardware o software per computer venisse rivoluzionato e tale compito potesse essere completato, allora questo sarebbe un approccio sistematico per provare o confutare molte questioni in sospeso in molti campi. Uno degli scopi di questo tipo di ricerca è stimolare nuove domande, non fornire nuove risposte.

Quando si tratta di calcolare S (5) in particolare, la sfida è una sfida di ricerca di base. La ricerca pura riguarda la risoluzione di problemi che non sono mai stati risolti, non si tratta di avere una grande applicazione. Nessuno ha ancora escogitato un modo per calcolare S (5) e poiché questa sequenza non è calcolabile è possibile che non ci sia modo per calcolare efficacemente questo numero. Essere in grado di calcolarlo, o di fornire una ragione per cui non può essere calcolato, sarebbe probabilmente un risultato pubblicabile: entrambi sono difficili e nessuno dei due è mai stato fatto prima.

Come esercizio pratico è una buona applicazione della teoria della computabilità e un contrappunto al problema dell'arresto. Il problema dell'arresto ci mostra che non esiste un singolo algoritmo che possa dirci se un programma arbitrario si interrompe, ma spesso è possibile dire se un programma specifico si fermerà. L'analisi di S (3) e S (4) ha richiesto un'analisi approfondita da parte di esperti per determinare se alcune macchine di Turing con 3 e 4 stati si fossero effettivamente fermate o meno. Questo non è realmente possibile con S (5), quindi per affrontare questo problema è necessario porre altre domande come "quali classi di programmi possiamo determinare se si arrestano o meno?".

Per vedere più chiaramente, prova questo post sul blog di Scott Aaronson del MIT. Un suo studente ha dimostrato che l'ottantesimo numero di castori occupati è inconoscibile dalla teoria degli insiemi standard. La matematica e la logica non possono calcolare questo numero, anche dato un tempo e uno spazio illimitati. Ecco una domanda molto ovvia e molto profonda a cui nessuno può rispondere: perché possiamo conoscere S (1), S (2), S (3) e S (4) in modo relativamente semplice, non possiamo dire se possiamo conoscere S (5), e possiamo dire con certezza che non possiamo conoscere S (8000)? Se potessi dirci la risposta avresti l'attenzione di molte persone intelligenti. Sforzarsi di fare il duro lavoro di calcolare S (5) è un passo per comprenderlo.

S (8000) è il primo elemento di questa sequenza che è inconoscibile? In caso contrario, qual è l'elemento più piccolo?

Due note: non sono un teorico, quindi tutta questa è la mia interpretazione. Prendilo con un pizzico di sale. In secondo luogo, un luogo migliore per questa domanda sarebbe lo scambio di stack di informatica. Adorano questa roba laggiù.

Vorrei fare un'ipotesi, che potrebbe non essere accurata per questo caso, ma che ha un intervallo più generale.

Se si cerca di calcolare S (5) con la forza bruta, probabilmente non è più interessante (ma molto più lungo) che risolvere un dato Sudoku con la forza bruta con un computer. Ma il punto di una domanda del genere è proprio che, essendo difficile, se si spera di rispondere bisogna cercare di essere intelligenti. È necessario trovare modi intelligenti per essere in grado di saltare il maggior numero di calcoli possibile rispetto a un approccio di forza bruta. In questo processo, si imparerà probabilmente qualcosa sugli oggetti coinvolti (ad esempio le macchine di Turing) e li capirà meglio. Bisogna anche essere intelligenti con i dettagli dell'implementazione, con il multi-threading, ecc.

Scegliamo di andare sulla Luna. Scegliamo di andare sulla Luna in questo decennio e fare le altre cose, non perché sono facili, ma perché sono difficili, perché quell'obiettivo servirà per organizzare e misurare al meglio le nostre energie e capacità, perché quella sfida è una che siamo disposti ad accettare, uno che non siamo disposti a rimandare e uno che intendiamo vincere, e anche gli altri. (JFK 1962)

Ricerche come questa tendono ad aprire le porte. Non si sa mai quali scoperte verranno costruite su di loro in futuro. Molte, molte scoperte moderne cruciali provengono da ricerche che all'epoca non sembravano avere alcun uso pratico.

Quindi finanziarlo ha dei vantaggi davvero pratici, oltre a quelli dovuti all '"acquisizione di pura conoscenza", specialmente se scegli quali fondi finanziare o esplorare in base a ciò a cui potrebbero riguardare. È come un investitore che investe in start-up. Non tutte le idee vanno da nessuna parte (ancora) ma, dato il supporto, una parte lo farà ... e alcune cambieranno i mondi.

Le onde radio sono un buon esempio di una scoperta pensata per essere completamente inutile per la pratica scopi - controlla cosa pensava Hertz dei loro usi pratici. Avrebbe potuto prevedere un mondo di radio media in ogni tasca, squadre di emergenza radio e squadre di lavoro coordinate, telefoni cellulari, navigatori satellitari, radar, forni a microonde, missioni spaziali remote e telecamere esplorative, Google Earth e WiFi, avrebbe pensato questo?

Idem teoria quantistica - sicuramente discutendo le idee arcane non solo di atomi ma quark e particelle più piccole, per non parlare del presupposto che possano fare cose strane come esistere e non esistere in posti diversi o un posto allo stesso tempo, è un inutile dibattito ipotetico sugli atomi e ipotetiche sottoparticelle più piccole troppo piccole per essere rilevanti per la vita di tutti i giorni, semmai lo è. Avanti veloce di 50 anni: il semiconduttore. Supermagnets. Superconduttori. Scanner MRI negli ospedali. Il tuo smartphone. Cavi sottomarini. Il laser. CD / DVD / Bluray. La rete. Quasi tutti i dispositivi informatici e i cavi ottici oggi ampiamente utilizzati. Qualsiasi altra cosa che utilizzi (o debba tenere in considerazione) il tunneling quantistico e altri comportamenti strani.

Idem lo strano crepitio della seta strofinata sull'ambra (elettricità), le sequenze di numeri apparentemente casuali generate da forme ellittiche ed entità modulari (il Teorema di Modularità e Fermat), tabelle di logaritmi e valori trigonometrici (i valori tabulati sono stati utilizzati da pre - matematici dell'età dei computer, e ad alcuni può essere sembrato inutile, ma senza di loro Keplero, Galileo, Newton e altri avrebbero fatto tutte le scoperte che hanno fatto?) Mendel ha passato anni a incrociare i piselli; uno spreco inutile e ossessivo di sforzi, finché non si avanza rapidamente verso la genetica, la comprensione del DNA, la terapia genica, il riso resistente alle malattie, il trattamento delle malattie mitocondriali, l'ereditarietà quando inizia a sembrare un po 'più significativa nella storia umana.

Matematicamente, lo stesso vale. Una differenza è che a volte devi calcolare i tuoi dati piuttosto che osservarli. Ma il principio è molto simile e lo è anche l'impatto.

È anche molto probabile che questo sia visto da coloro che sanno come un problema "interessante", che probabilmente non sarà del tutto un vicolo cieco o che è collegato in qualche modo ad altri problemi intrattabili.

Ho concluso che non esiste alcun valore pratico o addirittura teorico nella ricerca di questi numeri S (n): n> 5.

Forse a torto. Euclide ha studiato per la prima volta i numeri primi nel corso di 2000 anni e non hanno avuto un'applicazione concreta fino a pochi decenni fa (crittografia).

Ad ogni modo, se stai cercando una risposta reale, ti suggerisco di leggere alcuni documenti sull'argomento. La pagina di wikipedia ne elenca alcuni.

Sono completamente d'accordo con i matematici e i fisici tra il pubblico che hanno sottolineato che la matematica pura in passato ha talvolta portato a importanti progressi pratici. Anche se questo accade molto raramente, è assolutamente impossibile sapere quale sarà la gemma rara in anticipo, quindi devi finanziare molte ricerche alla fine inutili (o, più precisamente, inutili finora) se vuoi avere una possibilità per trovare dette gemme. Come ingegnere, ho familiarità con molte di quelle gemme del passato e non sarei in grado di fare il mio lavoro se non fossero accadute. Certamente non ho né le competenze né il temperamento per aver trovato quelle scoperte da solo!

Detto questo , come ingegnere, c'è un altro aspetto da considerare: costruire supercomputer è difficile. La semplice pratica ingegneristica di costruire il computer per fare questo può portare a miglioramenti e scoperte stesse, e anche se non lo fa, finanziare questa ingegneria significa avere molte più persone con molta più esperienza nel fare le cose. Questo è importante e molto, molto spesso trascurato.

Una recente domanda su Aviation Stack Exchange ha chiesto perché i moderni aerei militari impiegano così tanto tempo a produrre rispetto agli aerei militari dei decenni passati (dopotutto, quegli aerei avevano anche per aprire nuovi orizzonti e risolvere sfide estremamente difficili, utilizzando strumenti molto più basilari e la differenza di tempo è quasi un ordine di grandezza). Ci sono, ovviamente, molte ragioni, ma questa risposta in particolare mi ha colpito perché sottolinea l'importanza di avere una forza lavoro di ingegneria di grande esperienza:

Ingegneri esperti allora avevano lavorato su una dozzina di nuovi progetti (o più), quindi avevano sviluppato un istinto su come progettare quello successivo. Oggi si può essere fortunati ad averne portato in aria uno solo in una vita.

Quel risponditore racconta di come aveva effettivamente esercitato pressioni sulla sua azienda affinché realizzasse una progettazione rapida ed economica solo per dare agli ingegneri più pratica e più esperienza nel fare un progetto reale, che avere ingegneri migliori varrebbe il costo di un progetto completamente artificiale esercizio (non dovrebbe sorprendere che questo progetto non abbia ottenuto il semaforo verde).

Il fatto che poche persone in più abbiano costruito un supercomputer in più equivale al loro costo? Non lo so, ma è una cosa non trascurabile e dovrebbe essere considerata nell'analisi costi-benefici. Soprattutto dal punto di vista di una nazione, avere ingegneri qualificati è un vantaggio così evidente per una nazione che sospetto che pochissimi obietterebbero al concetto generale di tasse destinate ad avere ingegneri migliori.

Per definizione, la scienza non significa avere valore.

La scienza significa accumulare e organizzare la conoscenza .

Questo vale non solo per il problema del castoro occupato, ma anche per le cifre di Pi greco, le cifre del numero di Eulero, la teoria delle stringhe in fisica e la vita sessuale di Amphicoelias fragillimus.

Anche se un problema teorico non ha (ancora) applicazioni, le tecniche sviluppate per affrontarlo e le conoscenze acquisite lungo il percorso possono essere immensamente preziose e potenzialmente utili anche in aree apparentemente non correlate. Si può guardare alla storia della matematica per esempi di questo.

Oltre a questo, aggiungerò una potenziale applicazione per affrontare il problema del castoro indaffarato: Induzione di Solomonoff . In breve, l'induzione di Solomonoff è una teoria dell'inferenza induttiva generale basata sulla ponderazione di ipotesi in base alle dimensioni delle macchine di Turing che le producono. I formalismi teorici per l'intelligenza artificiale generale come AIXI si basano su di esso.

Affrontare il problema del castoro occupato è importante anche per aree come la programmazione induttiva (che costruisce automaticamente programmi per computer) e dimostrazione automatica di teoremi, poiché implica la dimostrazione delle proprietà (es. arresto o non arresto) di programmi per computer arbitrari. Vedere Autonomia del computer e durata delle prove, ad esempio.

Per estendere le risposte con un'altra prospettiva: la domanda fondamentale che la teoria della computabilità pone è "che tipo di funzioni sono calcolabili, dati alcuni presupposti semplici e ragionevoli e dati modelli di macchine che potrebbero essere istanziate nell'universo fisico?" (Voglio dire, "istanziato" in teoria, con alcuni avvertimenti pratici, ovviamente.)

Quindi un modo per guardare alle teorie della computabilità e della complessità computazionale è vederle come riguardanti alcune proprietà fondamentali del mondo. Perché alcune funzioni sono calcolabili e altre no, dato il modello standard della fisica? Cosa è calcolabile nel corso della vita dell'universo e cosa non lo è? Cosa rende possibili i computer quantistici e quali sono i loro limiti ultimi? Che tipo di computer potremmo aspettarci se la fisica fosse leggermente diversa? Che tipo di ipotesi è necessario fare per rendere possibile l'ipercalcolo?

È quindi possibile che queste teorie mirino a scoprire qualcosa di così profondo e fondamentale come la fisica teorica. In base a questa analogia, l'indagine sul fatto che la funzione Busy Beaver con argomento "5" sia calcolabile potrebbe essere confrontata con un singolo esperimento specifico sulle proprietà di alcune particelle esoteriche. Fornisce un po 'di informazioni su una natura fondamentale delle cose.

Il problema / gioco di Busy Beaver ha fornito un'applicazione molto tangibile nel suo contributo alla decisione del tempo di arresto di un insieme molto ampio di piccole macchine di Turing che, a loro volta, vengono utilizzate per calcolare un valore empirico distribuzione come approssimazione alla cosiddetta Distribuzione Universale che permette la stima della probabilità algoritmica di una stringa (cioè la probabilità di produrre una stringa con un programma per computer casuale i cui bit eseguibili sono il risultato, ad esempio, del lancio di una moneta). / p>

Tale distribuzione è stata definita miracolosa in passato (Google The miraculous universal distribution). Ciò è dovuto alle sue proprietà teoriche come il più potente predittore generico. Nel lavoro dell'Algorithmic Group e dell'Algorithmic Dynamics Lab che co-conduco insieme con l'aiuto e il contributo di diversi brillanti ricercatori, il Busy Beaver ha contribuito a produrre queste approssimazioni numeriche della probabilità algoritmica e ha avuto un impatto in aree come quella animale e cognizione umana, complessità dei grafi, biologia evolutiva, vita artificiale e biologia molecolare. Ecco alcuni suggerimenti (solo 2 con URL perché Academia non mi consente di aggiungere più link, gli altri puoi Google):

• Mutazioni algoritmicamente probabili riproducono aspetti di evoluzioni come tasso di convergenza, memoria genetica, modularità, esplosione di diversità ed estinzione di massa
• Picchi di complessità comportamentale umana all'età di 25 anni ( c'era molto clamore sui media al riguardo, e c'è un video su YouTube che spiega i risultati in modo molto semplice, un po 'troppo semplificato)
• Metodi di teoria dell'informazione e complessità algoritmica for NetworkBiology Correlation of Automorphism Group Size and TopologicalProperties with Program-size Complexity Evaluations of Graphs and Complex Networks

A sua volta, quella ricerca ha spinto i teorici ad aggiornare anche il loro lavoro! per esempio. questo documento:

• Un algoritmo probabilistico in qualsiasi momento per il problema dell'arresto

Tra molti altri, tra cui un articolo di Physica A sulla complessità dei grafici e un articolo sui seminari di biologia cellulare e dello sviluppo sulle applicazioni alla biologia molecolare e alle reti genetiche.

Questo perché il Busy Beaver è profondamente correlato ai concetti della Teoria Algoritmica dell'Informazione come il numero Chaitin Omega e la cosiddetta distribuzione di Solomonoff's-Levin (vedi Scholarpedia articolo).

Quindi, da un "gioco" completamente teorico alle applicazioni del mondo reale nel contesto dei problemi più urgenti della scienza!

I progetti di teoria dei numeri complessi vengono spesso approvati perché potrebbero avere qualche vantaggio crittografico. È stato fatto molto lavoro su funzioni e calcoli unidirezionali che richiedono notevoli risorse del computer. Un esempio concreto è il modulo di un esponente primo in un campo finito utilizzato nella crittografia a chiave pubblica RSA.

Inoltre, gran parte della ricerca in crittografia è classificata. Potrebbe esserci una ragione per cui questo progetto è stato approvato che è noto solo ai ricercatori e alle persone che approvano il progetto.

Alcune ricerche potrebbero aprire opportunità imprevedibili nei suoi campi gemelli. L'implementazione di sistemi beaver estremamente efficienti (poiché richiede molto tempo) potrebbe avere implicazioni in alcune altre importanti simulazioni. Non sto dicendo che il problema dei castori occupati non abbia valore, ma altri li hanno evidenziati abbastanza bene.

Questo tipo di vantaggio incrociato si verifica anche nei sistemi open source. Ricordo esplicitamente che la ricerca svolta su Linux per migliorare la durata della batteria dei dispositivi Android ha portato a un notevole risparmio sui costi dei supercomputer che girano su Linux poiché il loro costo maggiore è l'elettricità.