Articoli

11.4: Estensioni degli automi cellulari


Finora abbiamo discusso dei modelli CA nelle loro impostazioni più convenzionali. Ma ci sono diversi modi per "rompere" le convenzioni di modellazione, che potrebbero rendere CA più utile e applicabile ai fenomeni del mondo reale. Ecco alcuni esempi.

  • Automi cellulari stocastici: Una funzione di transizione di stato di CA non deve essere una rigorosa funzione matematica. Può essere un processo computazionale che produce l'output in modo probabilistico. CA con tali regole probabilistiche di transizione di stato sono chiamate stocastico CA, che svolgono un ruolo importante nella modellazione matematica di vari fenomeni biologici, sociali e fisici. Un buon esempio è un modello CA di processi epidemiologici in cui l'infezione di una malattia avviene stocasticamente (questo sarà discusso maggiormente nella sezione seguente).
  • Automi cellulari multistrato: Gli stati delle cellule non devono essere scalari. Invece, ogni posizione spaziale può essere associata a più variabili (cioè vettori). Tali configurazioni a valori vettoriali possono essere considerate una sovrapposizione di più livelli, ciascuno con un modello CA convenzionale a valori scalari. I modelli CA multistrato sono utili quando più specie biologiche o chimiche interagiscono tra loro in uno spazio-tempo. Ciò è particolarmente legato ai sistemi di reazione-diffusione che verranno discussi nei capitoli successivi.
  • Automi cellulari asincroni: L'aggiornamento sincrono è una caratteristica dei modelli CA, ma possiamo anche rompere questa convenzione per rendere le dinamiche asincrone. Sono possibili diversi meccanismi di aggiornamento asincrono, come l'aggiornamento casuale (una cella selezionata casualmente viene aggiornata ad ogni passaggio temporale), l'aggiornamento sequenziale (le celle vengono aggiornate in un ordine sequenziale predeterminato), l'aggiornamento attivato dallo stato (alcuni stati attivano l'aggiornamento delle celle vicine ), ecc. Si sostiene spesso che l'aggiornamento sincrono nei modelli CA convenzionali sia troppo artificiale e fragile rispetto a leggere perturbazioni nell'aggiornamento degli ordini, e in questo senso i comportamenti di un modello CA sincrono sono ritenuti più robusti e applicabili ai problemi del mondo reale . Inoltre, esiste una procedura per creare una CA asincrona in grado di emulare in modo robusto il comportamento di qualsiasi CA sincrona [43].

Automa cellulare

UN automa cellulare (pl. automi cellulari, abbreviato. circa) è un modello discreto di calcolo studiato nella teoria degli automi. Gli automi cellulari sono anche chiamati spazi cellulari, automi a tassellazione, strutture omogenee, strutture cellulari, strutture a tassellazione, e array iterativi. [2] Gli automi cellulari hanno trovato applicazione in vari settori, tra cui la fisica, la biologia teorica e la modellazione delle microstrutture.

Un automa cellulare è costituito da una griglia regolare di cellule, ciascuno in un numero finito di stati, ad esempio sopra e spento (in contrasto con un reticolo di mappe accoppiate). La griglia può essere in qualsiasi numero finito di dimensioni. Per ogni cella, un insieme di celle chiamato its quartiere è definito rispetto alla cella specificata. Uno stato iniziale (tempo T = 0) viene selezionato assegnando uno stato a ciascuna cella. Un nuovo generazione viene creato (avanzando T da 1), secondo alcuni fissi regola (generalmente, una funzione matematica) [3] che determina il nuovo stato di ogni cella in termini di stato attuale della cella e gli stati delle celle nelle sue vicinanze. Tipicamente, la regola per aggiornare lo stato delle celle è la stessa per ogni cella e non cambia nel tempo, e viene applicata a tutta la griglia contemporaneamente, [4] sebbene siano note eccezioni, come l'automa cellulare stocastico e l'automa cellulare asincrono .

Il concetto è stato originariamente scoperto negli anni '40 da Stanislaw Ulam e John von Neumann mentre erano contemporanei al Los Alamos National Laboratory. Sebbene sia stato studiato da alcuni durante gli anni '50 e '60, è stato solo negli anni '70 e con Game of Life di Conway, un automa cellulare bidimensionale, che l'interesse per l'argomento si è espanso oltre il mondo accademico. Negli anni '80, Stephen Wolfram si impegnò in uno studio sistematico di automi cellulari unidimensionali, o quelli che chiama automi cellulari elementari, il suo assistente di ricerca Matthew Cook dimostrò che una di queste regole è Turing-complete. Wolfram pubblicato Un nuovo tipo di scienza nel 2002, sostenendo che gli automi cellulari hanno applicazioni in molti campi della scienza. Questi includono processori per computer e crittografia.

Le classificazioni primarie degli automi cellulari, come delineato da Wolfram, sono numerate da uno a quattro. Sono, nell'ordine, automi in cui i modelli generalmente si stabilizzano nell'omogeneità, automi in cui i modelli evolvono in strutture per lo più stabili o oscillanti, automi in cui i modelli evolvono in modo apparentemente caotico e automi in cui i modelli diventano estremamente complessi e possono durare per lungo tempo, con stabili strutture locali. Si pensa che quest'ultima classe sia computazionalmente universale o in grado di simulare una macchina di Turing. Tipi speciali di automi cellulari sono reversibile, dove solo una singola configurazione porta direttamente a una successiva, e totalistico, in cui il valore futuro delle singole celle dipende solo dal valore totale di un gruppo di celle vicine. Gli automi cellulari possono simulare una varietà di sistemi del mondo reale, compresi quelli biologici e chimici.


Automi cellulari semplici su un foglio di calcolo Spread

Gli automi cellulari (CA) possono essere utilizzati per illustrare come l'ordine a livello macro possa derivare da interazioni a livello micro. Sebbene sia possibile eseguire semplici CA utilizzando carta e matita, un computer è in grado di tenere traccia di tutte le interazioni. Questo documento illustra come semplici CA possono essere eseguite su un foglio di calcolo, utilizzando come esempio la diffusione di un'innovazione di prodotto.

Introduzione

Questo documento dimostra l'implementazione di un automa cellulare (CA) su un foglio di calcolo. I modelli CA forniscono una chiara dimostrazione di un fenomeno noto come ordine di emergenza, derivante dall'interazione di agenti piuttosto che come risultato di un controllo centralizzato. Forse l'applicazione più nota di un modello di tipo automa cellulare nelle scienze sociali è il modello di segregazione razziale di Thomas Schelling (Schelling, 1971), sebbene gli AC possano anche essere usati per modellare la diffusione di innovazioni o la diffusione di voci, per citare solo due applicazioni. Gaylord e D’Andria (1998), Hegselmann e Flache (1998) e Gilbert e Troitzsch (1999) discutono ulteriori applicazioni delle AC nelle scienze sociali, mentre Torrens (2000) esamina l'uso delle AC nello studio dei sistemi urbani.

Cosa sono gli automi cellulari?

Gli automi cellulari sono modelli dinamici di interazioni locali tra cellule su una normale griglia d-dimensionale. Ogni cella può trovarsi in uno di un numero predeterminato di stati (ad esempio acceso o spento, vivo o morto). Man mano che la simulazione procede passo dopo passo, lo stato in cui si trova una particolare cella dipende dal suo stato nel periodo precedente e dallo stato dei suoi immediati vicini secondo una semplice regola. Questa regola viene applicata a tutte le celle della griglia. Le celle vicine sono spesso definite come le otto celle che circondano la cella, note come quartiere di Moore, o come le celle direttamente sopra, sotto, a sinistra e a destra della cella, note come quartiere di von Neumann (vedi Gilbert e Troitzsch, 1999). I quartieri di von Neumann e Moore sono mostrati in Figura 1.

Figura 1. Quartieri CA.

Una delle applicazioni più note di un automa cellulare è il Gioco della Vita (vedi, ad esempio, Waldrop, 1992 Holland, 1998). Nel Gioco della Vita, una cellula sopravvive solo se due o tre dei suoi vicini sono vivi. Se ci sono più o meno vicini vivi, la cellula muore, sia per il sovraffollamento che per la solitudine. Una cellula morta viene riportata in vita se ha tre vicini vivi. Da queste semplici regole emergono una miriade di schemi in continua evoluzione. (nota 1) Mentre è certamente possibile condurre piccole simulazioni a mano – come racconta Casti (1994), le prime esecuzioni del modello di segregazione di Schelling usavano una lavagna da disegno – è molto più facile usare un computer. Non è sempre necessario scrivere un programma per computer per implementare una CA. I modelli CA possono essere implementati anche utilizzando pacchetti software come Mathematica (vedi Gaylord e D’Andria, 1998) e StarLogo (Resnick, 1997). Tuttavia, le CA semplici (cioè quelle in cui una cella può trovarsi in uno dei due stati) possono essere modellate su un foglio di calcolo. Un modello di foglio di calcolo mostra il funzionamento interno della CA e offre al modellatore il controllo diretto sul modello, senza la necessità di competenze di programmazione.

Un esempio generale: il modello di diffusione

Gli automi cellulari sono sempre più utilizzati in economia, specialmente nei modelli economici urbani/spaziali. Macken e Randall (1994) hanno utilizzato il concetto per sviluppare un modulo ‘Privatizzazione e nazionalizzazione’ nel pacchetto di apprendimento assistito da computer WinEcon. Inoltre, le AC possono essere applicate a qualsiasi situazione di interazione locale, come la diffusione di informazioni o voci, modelli di formazione dell'opinione o l'adozione di nuove tecnologie. Questa sezione mostra un modello di diffusione su una griglia 10 x 10. Ogni cella rappresenta un individuo che può trovarsi in uno dei due stati: potrebbe aver sentito parlare del nuovo prodotto (queste celle sono colorate di nero) e potrebbe non averlo (queste celle sono colorate di bianco). Una singola cella diventa nera se uno dei suoi quattro vicini di von Neumann è colorato di nero. Questa regola può essere implementata utilizzando la funzione ’s ‘if’ di Excel.

Per iniziare, seleziona una griglia di celle 10 x 10 come stato iniziale della CA. Le celle in questo caso rappresentano agenti economici. Una cella contiene il valore 1 se un agente ha adottato una nuova innovazione e contiene 0 altrimenti. La funzione ‘if’ che incapsula la regola CA viene inserita in ogni cella di una griglia identica immediatamente sotto la prima griglia. In generale, per una data cella e, con i vicini a, b, c e d, la funzione ‘if’ è:

dove il pedice i si riferisce allo stato della cella nella griglia iniziale. Per le celle al centro della griglia, questo è facile da implementare. Tuttavia, è necessario prestare un po' più di attenzione con le celle nelle righe superiore e inferiore e nelle colonne all'estrema sinistra e destra. Quartieri di celle nelle righe superiore e inferiore e nelle colonne all'estrema sinistra e destra ‘avvolgi’ la griglia, quindi per una cella nella riga superiore, il suo vicino ‘nord’ apparirà nella parte inferiore riga della griglia. Allo stesso modo, il vicino ‘western’ di una cella nella colonna di estrema sinistra della griglia si trova nella colonna di estrema destra, come mostrato nella Figura 2.

Figura 2: Quartieri CA avvolgenti.

La seconda griglia (contenente le formule) mostra lo stato della CA dopo la prima iterazione. Ulteriori iterazioni possono essere ottenute copiando la griglia e incollando la pagina. Finché viene mantenuta la stessa spaziatura tra le griglie, le formule si aggiorneranno automaticamente.

Non è facile individuare modelli in un intervallo di 0 e 1. Per semplificare le cose, la funzione ‘if’ può essere utilizzata nuovamente per creare una griglia di celle vuote e piene utilizzando la seguente formula:

La Figura 3 mostra la configurazione iniziale per la CA.

Figura 3: Configurazione dell'automa cellulare.

Lo stato iniziale della CA è mostrato nelle celle da D4 a M13. In questo esempio, solo 1 dei 100 agenti ha acquistato il nuovo bene. Le funzioni ‘if’ contenenti le regole della CA sono inserite nelle celle da D15 a M24. Accanto a questi due blocchi di celle ci sono altre due griglie che mostrano le stesse informazioni, usando un # per rappresentare 1 e uno spazio vuoto per rappresentare 0, secondo la funzione ‘if’ descritta nell'equazione (3). Per vedere come si diffonde la nuova innovazione, le formule nelle celle da D15 a M24 possono essere copiate e incollate lungo la pagina, con una riga vuota tra ogni copia. Senza questa riga vuota, le formule non faranno riferimento alle celle corrette. In questo esempio, l'innovazione si diffonde in tutta la griglia in sole nove iterazioni, come mostrato nella Figura 4.

Figura 4: Il modello di diffusione.

Il modello standard del ciclo di vita/diffusione del prodotto suggerirebbe che un grafico delle vendite cumulative dovrebbe tracciare una curva come la curva logistica (vedi, ad esempio, Bass, 1969). Un grafico degli acquisti cumulativi (ovvero il numero di celle contenenti 1 in ciascun periodo) derivato dalla simulazione CA produce anche una curva di tipo logistico, come mostrato nella Figura 5.

Figura 5: Acquisti cumulativi nella simulazione CA.

Estensioni al modello

Il modello deterministico presentato sopra non è realistico, poiché una volta che un agente ha acquistato il nuovo articolo, lo faranno anche tutti gli altri. Il modello può essere esteso introducendo un elemento stocastico nel modo in cui una cellula è influenzata dai suoi vicini. In questo modello, una cella vuota viene riempita con una data probabilità se viene riempita almeno una delle sue vicine. Ciò si ottiene su un foglio di calcolo utilizzando il generatore di numeri casuali di Excel per creare un numero casuale compreso tra 0 e 1 per ciascun agente (ogni cella). Una cella piena influenzerà la sua vicina se il valore casuale ad essa assegnato è inferiore al livello di probabilità specificato. La regola CA diventa quindi:

dove rJ(J=a,b,c,d) è un numero casuale compreso tra 0 e 1 associato alla cella J e P è 1 meno la probabilità data. Definizione P come 1 meno la probabilità data consente di scrivere la formula come sopra. Se il dato livello di probabilità fosse inserito direttamente nella formula =if(a*run<p,1…), Excel considererà tutte le celle vuote (dato il valore 0) come conformi a questo criterio e restituirà un valore di 1 per ogni cella. L'agente rappresentato da cell e adotterà la nuova innovazione se almeno una cella vicina ha adottato e il numero casuale associato a quella vicina supera il livello di probabilità scelto P. La schermata seguente mostra questa nuova CA, con lo stato iniziale della griglia nelle celle E5..N14, le formule inserite nelle celle E16..N25 e i numeri casuali inseriti nelle celle P16..Y25.

Figura 6: modello di diffusione CA modificato.

Come sopra esposto, una volta inserite le formule, è facilmente riscontrabile l'effetto di una variazione della probabilità. Si noti che la probabilità che una cella vuota venga riempita è 1 meno il livello di probabilità immesso nella cella F2. Per una probabilità sufficientemente alta (valori sufficientemente bassi inseriti nella cella F2), il grafico dell'adozione cumulativa assomiglia al grafico logistico previsto nel modello del ciclo di vita del prodotto, come mostrato nella Figura 7. Va notato, tuttavia, che questi grafici sono stati ottenuti da un Modello CA con la stessa griglia di numeri casuali e distribuzione iniziale degli adottanti nel periodo 1.

Figura 7: L'estensione della diffusione con probabilità selezionate.

Nel modello di diffusione stocastica, non è garantito che una nuova innovazione si diffonda tra tutti gli agenti. Questo può essere dimostrato tenendo premuto P costante ed eseguendo la simulazione un numero di volte utilizzando uno stato iniziale diverso per ogni esecuzione.

L'esecuzione della simulazione dieci volte con una probabilità del 70% che una cella vuota venga riempita se viene riempita una delle sue vicine e con una cella diversa dato il valore 1 nella griglia iniziale in ogni esecuzione, ha prodotto i risultati mostrati nella Figura 8.

Figura 8: L'effetto di diverse configurazioni di partenza (P = 70%).

In questo esempio, finché ci sarà un numero sufficiente di early adopter, l'innovazione si diffonderà nella maggior parte della rete. Laddove questo supporto iniziale non venga raggiunto, l'adozione è limitata a pochi o in alcuni casi a un solo agente sulla rete.

Conclusione

I modelli CA possono essere utilizzati per dimostrare come i grafici caratteristici del ciclo di vita del prodotto emergano dal comportamento dei singoli agenti e come il modello regga ancora se una cellula è influenzata dai suoi vicini con una probabilità sufficientemente alta. Questa è, tuttavia, solo una potenziale applicazione degli automi cellulari in economia e in altre scienze sociali. Gli esempi descritti da Gilbert e Troitzsch (1999), come il Game of Life e il modello maggioritario, possono essere riprodotti su un foglio di calcolo con altrettanta facilità (vedi appendice). Un vantaggio dell'utilizzo di un foglio di calcolo per studiare gli automi cellulari è che il funzionamento del modello è reso esplicito. Le ipotesi impiegate e la relazione tra le celle sono incapsulate nelle formule utilizzate. I modelli CA di fogli di calcolo sono limitati a esempi relativamente semplici, ma forniscono la stessa quantità di controllo sul modello di un programma CA scritto, ad esempio, in Visual Basic, senza la necessità di competenze di programmazione. Inoltre, questi modelli di CA possono fornire una facile introduzione alla nozione che l'ordine può emergere in un sistema di agenti interagenti, come un mercato, puramente come risultato di interazioni dinamiche. I modelli CA di fogli di calcolo potrebbero quindi essere utilizzati come una semplice introduzione ai modelli basati su agenti e alla modellazione in economia, come sostenuto di recente da Ormerod (2003).

Appendice: il modello maggioritario

Nel modello maggioritario, una cella cambierà da bianca a nera se la maggior parte dei suoi vicini è nera. Si potrebbe vedere questo modello come una variazione del modello di diffusione piuttosto che adottare il nuovo prodotto quando un vicino lo ha adottato, ogni agente aspetta che la maggioranza dei suoi vicini lo abbia adottato. I modelli del foglio di calcolo mostrano che anche con preferenze modeste (cioè la cella che cambia per corrispondere a poco più della metà delle sue vicine), le celle formano blocchi solidi distinti. Questo ricorda la scoperta di Schelling che le comunità possono diventare segregate razzialmente anche quando ogni agente ha solo una lieve preferenza per i vicini della propria razza. La versione del modello di maggioranza mostrata qui impiega il quartiere di Moore (8 vicini) piuttosto che il quartiere di von Neumann impiegato negli esempi sopra. Ogni cella può trovarsi in uno dei due stati iniziali, indicati con 1 e 0. Se la somma delle celle vicine è maggiore o uguale a 5, la cella passa (o rimane) nello stato 1, mentre se la somma è minore o uguale a 4, la cella passa (o rimane) nello stato 0. Questa regola può essere implementata con la funzione ’s ‘if’ di Excel, come nel modello di diffusione. Una schermata del modello maggioritario è mostrata nella Figura A1.

Lo stato iniziale di ogni cella viene mostrato nelle celle B2–P16 e le formule ‘if’ vengono immesse nelle celle B18–P32, pronte per essere copiate nella pagina. Questo particolare esempio raggiunge il suo stato stazionario dopo 10 iterazioni. Le configurazioni iniziale e finale delle celle sono mostrate in Figura A2.

Figura A1: il modello maggioritario

Figura A2: il modello maggioritario

Riferimenti

Bass, F. M. (1969) ‘Un nuovo modello di crescita del prodotto per i beni di consumo durevoli’, Scienze della gestione, 15, pp. 215󈞇.

Casti, J. (1994) Complessificazione, Londra: Abaco.

Gaylord, R.J. e D’Andria, L.J. (1998) Simulazione della società: un toolkit matematico per modellare il comportamento socioeconomico, Berlino: TELOS Springer-Verlag.

Gilbert, N. e Troitzsch, K. G. (1999) Simulazione per lo scienziato sociale, Buckingham: Open University Press

Hegselmann, R. e Flache, A. (1998) ‘Comprendere le dinamiche sociali complesse: un appello per la modellazione basata sugli automi cellulari’, Journal of Artificial Societies and Social Simulation, 1(3), [in linea] disponibile su: http://www.soc.surrey.ac.uk/JASSS/1/3/1.html .

Olanda, JH (1998) Emergenza, dal caos all'ordine, Oxford: Oxford University Press.

Macken, K. e Randall, K. (1994) ‘Insegnare e apprendere l'economia utilizzando gli automi cellulari in Asymmetrix Toolbox’, Computer nella revisione dell'istruzione superiore, 8(3), pag. 12.

Ormerod, P. (2003) ‘Invertire la tendenza: portare l'insegnamento dell'economia nel ventunesimo secolo’, Rivista internazionale di educazione economica, vol. 1, [in linea] disponibile all'indirizzo http://www.economicsnetwork.ac.uk/iree/i1/ormerod.htm .

Resnick, M. (1997) Tartarughe, termiti e ingorghi stradali: esplorazioni in micromondi massicciamente paralleli, Cambridge, MA: MIT Press.

Schelling, T. C. (1971) ‘Modelli dinamici di segregazione’, Rivista di sociologia matematica, 1, pp. 143󈟂.

Torrens, P. M. (2000) ‘Come funzionano i modelli cellulari dei sistemi urbani (1. teoria)’, Center for Advanced Spatial Analysis (CASA) Working Paper n. 28, University College di Londra.

Waldrop, M. (1992) Complessità, la scienza emergente ai margini dell'ordine e del caos, Londra: pinguino.

Dettagli del contatto

Chris Hand, ricercatore post-dottorato
Facoltà di Economia
Università di Kingston
Kingston sul Tamigi
Surrey KT2 7LB


Nanodispositivi

7.4.5 Automi cellulari a punti quantici (QCA)

Il QCA utilizza array di punti quantici accoppiati per implementare funzioni logiche booleane [269] . Un singolo punto quantico può avere un diametro dell'ordine di 10 nm, quindi i dispositivi QCA sono molto piccoli. La Fig. 7.13 mostra il concetto di base. Quattro punti quantici accoppiati da barriere tunnel sono posizionati in una matrice quadrata. Questo costituisce una cella QCA. Gli elettroni possono creare tunnel tra i punti ma non possono lasciare la cella. Due elettroni sono posti in ogni cella La repulsione di Coulomb assicura che occupino gli angoli opposti. Quindi, ci sono due configurazioni di stato fondamentale con la stessa energia che possono essere etichettate come 0 e 1. La Fig. 7.14 mostra diversi semplici dispositivi QCA. A sinistra abbiamo fili, un inverter e a destra un cancello maggioritario. In ogni caso, la configurazione delle celle adiacenti è determinata minimizzando la repulsione di Coulomb. Tutte le funzioni logiche possono essere implementate utilizzando la porta maggioritaria e l'inverter.

FIGURA 7.13. Un'illustrazione del concetto di automa cellulare quantistico. Quattro punti quantici disposti in un quadrato e occupati da due elettroni hanno due possibili polarizzazioni dello stato fondamentale (quadrati sinistro e destro), assegnati per rappresentare "0" e "1".

FIGURA 7.14. Alcuni dispositivi QCA. A sinistra, un filo (celle 1-3) conduce l'ingresso (cella 1) al fanout (celle 3, 4 e 6). Quando i fili paralleli sono combinati (celle 5 e 7 convergenti sulla cella 8), l'uscita (cella 9) è invertita. Sulla destra abbiamo due ingressi (diciamo le celle 1 e 2) e un ingresso di programmazione (diciamo la cella 3). La cella centrale 4 non può minimizzare tutte le repulsioni coulombiane cella-cella ma sceglie la configurazione che minimizza la repulsione complessiva. A seconda dell'ingresso di programmazione, l'uscita (cella 5, imitando la configurazione della cella 4) è quella della funzione logica AND o OR.


Indice KDD Nuggets

Le iscrizioni sono le benvenute e devono essere inviate tramite e-mail, con a
DESCRITTIVO riga dell'oggetto (e un URL) a gps.
Si prega di mantenere brevi gli annunci relativi alla CFP e alle riunioni e fornire
un URL per i dettagli.

-- Gregory Piatetsky-Shapiro (a cura di)
GPS

******************** Esclusione di responsabilità ufficiale *************************
Tutte le opinioni qui espresse sono quelle dei contributori e non
necessariamente dei rispettivi datori di lavoro (o di KD Nuggets)
*********************************************************************


Se lo sciocco persistesse nella sua follia, diventerebbe saggio.
William Blake
Precedente 1 Successivo Inizio
Precedente 2 Successivo Inizio Inizio Da: 'IMLM Workshop (pkc)' ([email protected])
Oggetto: CFP: numero speciale MLJ su IMLM

Ecco un CFP per il numero speciale di Machine Learning Journal su IMLM.
La presentazione è prevista per il 1 ottobre 97. Spero che tu possa inviare. Grazie.

Giornale di apprendimento automatico
Numero speciale su


Integrazione di più modelli appresi
per il miglioramento e la scalabilità degli algoritmi di apprendimento automatico


La maggior parte delle moderne tecniche di apprendimento automatico, statistiche e KDD utilizzano a
singolo modello o algoritmo di apprendimento alla volta, o al massimo selezionane uno
modello da un insieme di modelli candidati. Di recente, tuttavia, c'è stato
notevole interesse per le tecniche che integrano il collettivo
previsioni di un insieme di modelli in qualche modo di principio. Con così
tecniche spesso l'accuratezza predittiva e/o l'addestramento
l'efficienza dell'intero sistema può essere migliorata, poiché si può "mischiare"
e match' tra i punti di forza relativi dei modelli che vengono combinati.

Qualsiasi aspetto dell'integrazione di più modelli è appropriato per il
problema speciale. Tuttavia intendiamo che il focus del numero speciale sia
sui temi del miglioramento dell'accuratezza delle previsioni e del miglioramento della formazione
efficienza nel contesto di grandi banche dati.


Le candidature sono ricercate, ma non limitate a, i seguenti argomenti:

1) Tecniche che generano e/o integrano più apprendimenti
Modelli. Esempi sono schemi che generano e combinano
modelli di

* utilizzando diverse distribuzioni di dati di allenamento
(in particolare mediante l'addestramento su diverse partizioni
dei dati)
* utilizzando diverse tecniche di campionamento per generare differenti
partizioni
* utilizzando diversi schemi di classificazione dell'output
(ad esempio utilizzando i codici di output)
* utilizzando diversi iperparametri o euristiche di addestramento
(principalmente come strumento per generare più modelli)

2) Sistemi e architetture per implementare tali strategie.
Per esempio,

* sistemi di apprendimento multipli paralleli e distribuiti
* apprendimento multi-agente su dati intrinsecamente distribuiti

3) Tecniche che analizzano l'integrazione di più modelli appresi per

* selezione/potatura modelli
* stima della precisione complessiva
* confrontare diversi metodi di integrazione
* compromesso tra accuratezza e semplicità/comprensione

1 ottobre: ​​Scadenza per la presentazione
15 dicembre: Scadenza per la restituzione delle decisioni agli autori
15 marzo: Scadenza per gli autori per inviare le versioni finali
Agosto 1998: Pubblicazione

1) I manoscritti devono essere conformi alle istruzioni di formattazione in:

Il primo autore sarà il contatto principale se non diversamente specificato.

2) Gli autori dovranno inviare 5 copie del manoscritto a:

Karen Cullen
Ufficio Editoriale Machine Learning
All'attenzione: numero speciale su IMLM
Kluwer Academic Press
101 Philip Drive
Parco Assinippi
Norwell, MA 02061
617-871-6300
617-871-6528 (fax)
[email protected]

Filippo Chan
Numero speciale MLJ su IMLM
Informatica
Florida Institute of Technology
150 W. University Boulevard.
Melbourne, FL 32901
407-768-8000 x7280 (x8062) (407-674-7280/8062 dopo il 6/1/97)
407-984-8461 (fax)

3) Si prega di inviare anche un frontespizio ASCII (titolo, autori, email, abstract,
e parole chiave) e una versione poscritta del manoscritto a
[email protected]

Si prega di indirizzare richieste generali a:

Le informazioni aggiornate sono mantenute sul WWW all'indirizzo:

Philip Chan, Florida Institute of Technology [email protected]
Salvatore Stolfo, Columbia University [email protected]
David Wolpert, IBM Almaden Research Center [email protected]

Precedente 3 Successivo Inizio [Il seguente è un annuncio commerciale. GPS]

Da: "Spedding, Patrick" ([email protected])
Oggetto: Lo scenario di Cognos vince il premio Analyst's Choice di PC Week Labs
Data: Ven, 9 maggio 1997 05:36:20 -0400

Lo scenario di Cognos vince il premio Analyst's Choice di PC Week Labs

BURLINGTON, Massachusetts, 6 maggio /PRNewswire/ -- Cognos'(R) (Nasdaq: COGNF
Toronto: CSN)

Lo strumento di data mining Scenario(TM) ha vinto il PC Week Labs Analyst's
Choice Award dopo un confronto diretto con un prodotto concorrente. Scenario
'l'interfaccia innovativa lo rende il pacchetto software più interessante che abbiamo mai visto
quest'anno,' ha detto la recensione, che ha citato la sua superiorità, potenza e grafica.
Scenario estende la business intelligence più completa del settore
famiglia di prodotti, unendosi a PowerPlay®, leader di mercato di Cognos, il
client OLAP universale e query e reportistica Impromptu® pluripremiate
attrezzo.

"Questo premio conferma la convinzione di Cognos che il data mining nel in
mani degli utenti aziendali offre un potente, funzionale e conveniente
vantaggio competitivo", ha affermato Alan Rottenberg, vicepresidente senior, Business
Prodotti di intelligenza. "Mettere le capacità di data mining nelle mani dei decisori
e i lavoratori della conoscenza ampliano la nostra strategia per consentire loro di reagire
rapidamente a nuove conoscenze, sia nei sistemi operativi che nei dati
magazzini.
Scenario si unisce agli altri pluripremiati strumenti di business intelligence di Cognos
per ottenere risultati più rapidi, costi di proprietà più bassi e facilità senza precedenti
d'uso.'
PC Weeks Labs, il più grande laboratorio di test indipendente al mondo,
ha applaudito sia lo Scenario di Cognos che il concorrente per aver portato nuovi dati
tecniche di mining al PC. "Ma nei test testa a testa", ha scritto,
"Scenario ha estratto in sicurezza più informazioni utilizzabili rispetto al suo concorrente,
rendendolo la nostra prima scelta.'
Progettato per individuare modelli ed eccezioni nei dati aziendali che
potrebbe
altrimenti da perdere, la sofisticata interfaccia di Scenario consente agli utenti di
visualizzare prontamente le informazioni aziendali scoperte. è
automatizza il
scoperta e classificazione dei fattori critici che incidono su un'azienda, espone
relazioni nascoste tra fattori e stabilisce soglie e parametri di riferimento.
Uno strumento desktop intuitivo ed economico, Scenario libera il data mining
da quello che è tipicamente un processo costoso e dispendioso in termini di tempo. Approfondimenti
derivati ​​usando Scenario sono raggiunti direttamente da quelli meglio posizionati per
utilizzare la conoscenza ed effettuare un rapido cambiamento.
Scenario 1.0, rilasciato nell'aprile 1997, è disponibile da Cognos per
$695.
Funziona su Windows 95 e Windows NT e richiede un 486 . compatibile con IBM
PC e 8 MB di RAM.

Precedente 4 Successivo Inizio Data: Mer, 7 maggio 1997 11:46:09 -0700 (PDT)
Da: Finanza Computazionale ([email protected])
Oggetto: Programmi di laurea in finanza computazionale
=======================================================================

FINANZA COMPUTAZIONALE presso l'Oregon Graduate Institute of Science &
Tecnologia (OGI)

Master of Science Concentrazioni in
Informatica e ingegneria (CSE)
Ingegneria Elettrica (EE)

Prossima scadenza per la domanda di MS per l'autunno 1997: 15 maggio e 15 giugno!

Nuovo! Programma di certificazione progettato per studenti part-time.

Panoramica sulla finanza computazionale:

I progressi nella tecnologia informatica ora consentono l'uso diffuso di
tecniche di analisi sofisticate e computazionalmente intensive applicate a applied
finanza e mercati finanziari. L'analisi in tempo reale tick-by-tick
dati dei mercati finanziari e la gestione in tempo reale dei portafogli di
migliaia di titoli stanno ora investendo il settore finanziario. Questo ha
ha aperto nuove opportunità di lavoro per scienziati, ingegneri e computer
professionisti della scienza nel campo della finanza computazionale.

La forte domanda all'interno del settore finanziario per tecnicamente
laureati sofisticati è rivolto all'OGI dal Master of Science e
Programmi di certificazione in finanza computazionale. A differenza di uno standard di due anni
MBA, i programmi sono diretti alla formazione di scienziati, ingegneri e
professionisti finanziari tecnicamente orientati nell'area dei quantitativi
finanza.

I programmi del master portano a un Master of Science in Computer Science e
Ingegneria (traccia CSE) o in Ingegneria Elettrica (traccia EE). La MS
i programmi possono essere completati entro 12 mesi a tempo pieno. Nel
Inoltre, OGI ha introdotto un programma di certificati progettato per fornire
professionisti in ingegneria e finanza un mezzo per aggiornare le proprie competenze
o acquisire nuove competenze nella finanza quantitativa a tempo parziale.

Le concentrazioni di Computational Finance MS presentano una combinazione unica
di corsi che fornisce una solida base in finanza a un non banale,
livello quantitativo, oltre alle conoscenze e competenze di base essenziali di
informatica o le aree della tecnologia dell'informazione di elettrico
ingegneria. Queste competenze sono importanti per l'analisi avanzata dei mercati
e per lo sviluppo di analisi di investimento all'avanguardia, portafoglio
sistemi di gestione, negoziazione, pricing dei derivati ​​e gestione del rischio.

Il MS in CSE è la preparazione ideale per gli studenti interessati a garantire
posizioni nei sistemi informativi del settore finanziario, mentre il MS
in EE fornisce una formazione rigorosa per gli studenti interessati a perseguire
carriere come analisti quantitativi presso società finanziarie all'avanguardia.

Il curriculum è fortemente orientato al progetto, utilizzando lo stato dell'arte
strutture informatiche e dati in tempo reale/storici dalle principali società del mondo
mercati finanziari forniti da Dow Jones Telerate. Gli studenti sono formati in
l'uso di pacchetti software numerici e analitici di alto livello per
analizzare i dati finanziari.

OGI si è affermata come istituzione leader nella ricerca e
formazione in finanza computazionale. Inoltre, OGI ha una forte ricerca
programmi in una serie di aree che sono altamente rilevanti per il lavoro in
analisi quantitativa e sistemi informativi nel settore finanziario.

Precedente 5 Successivo Inizio Data: mar, 13 maggio 1997 14:40:06 +0100 (BST)
Da: [email protected] (George Smith)
Oggetto: posizione di assistente di ricerca presso UEA, Norwich, UK,

La Scuola di Sistemi Informativi, Università dell'Est
Anglia, Norwich ha un posto vacante per a

lavorare su un progetto dal titolo 'Datamining in the
settore delle telecomunicazioni».


Un laureato in informatica con almeno una laurea 2(I) in informatica
o si cerca un soggetto alleato per un posto di due anni
a partire dal 1 agosto 1997, o non appena possibile
successivamente.

L'incaricato lavorerà all'interno di una delle principali telecomunicazioni
società, Nortel plc, su base quotidiana ma
sarà un dipendente dell'Università dell'East Anglia.
Ci saranno opportunità per la registrazione per un part-time
grado superiore presso l'Università. Un candidato prescelto lo farà
ci si aspetta che abbia un alto grado di calcolo e
un forte background informatico. Sarà data la preferenza a
coloro che, inoltre, hanno qualche conoscenza
(e competenza) in uno o più dei seguenti:
calcolo evolutivo, ricerca operativa, artificiale
intelligence o telecomunicazioni.

La ricerca è patrocinata congiuntamente dalla Società Didattica
Schema e da Nortel plc e coinvolge il
sviluppo e applicazione di varie inferenze e
tecniche euristiche, inclusi algoritmi genetici,
ricottura simulata e ricerca tabù, per suscitare conoscenza
da set di dati su larga scala generati all'interno del
settore delle telecomunicazioni.

Stipendio iniziale da definire ma dovrebbe essere intorno
16K sterline inglesi.

I candidati sono invitati a telefonare al dottor George D Smith (+44
(0) 1603 593260) o inviare un'e-mail a [email protected] per
ulteriori informazioni.

Domande sotto forma di lettera di accompagnamento più tre
copie di un CV, compresi i nomi e gli indirizzi di
tre arbitri, devono essere inviati a:

Il dottor George D Smith
Scuola di Sistemi Informativi
Università dell'East Anglia
Norwich
NR4 7TJ, Regno Unito

entro venerdì 6 giugno 1997.

La seconda conferenza Pacifico-Asia su

La seconda conferenza Pacifico-Asia sulla scoperta della conoscenza e dei dati
Mining (PAKDD-98) fornirà un forum internazionale per la condivisione
di risultati di ricerca originali ed esperienze pratiche di sviluppo
tra ricercatori e sviluppatori di applicazioni di diversi KDD
aree correlate come l'apprendimento automatico, i database, le statistiche,
acquisizione della conoscenza, visualizzazione dei dati, reingegnerizzazione del software,
e sistemi basati sulla conoscenza. Seguirà il successo di PAKDD-97
tenutosi a Singapore nel 1997 riunendo partecipanti di
università, industria e governo.

I documenti su tutti gli aspetti della scoperta della conoscenza e del data mining sono
benvenuto. Le aree di interesse includono, ma non sono limitate a:

- Riduzione dei dati e della dimensionalità
- Algoritmi e strumenti di data mining
- Data Mining e Data Warehousing
- Data Mining su Internet
- Metriche di data mining
- Pre-elaborazione e post-elaborazione dei dati
- Visualizzazione di dati e conoscenze
- Deduzione e Induzione in KDD
- Discretizzazione dei dati continui
- Data mining distribuito
- Framework e processo KDD
- Rappresentazione e acquisizione della conoscenza in KDD
- Riutilizzo della conoscenza e ruolo della conoscenza del dominio
- Acquisizione di conoscenze in Software Re-Engineering e Software
Sistemi di informazione
- Induzione di regole e alberi decisionali
- Problemi di gestione in KDD
- Apprendimento automatico, aspetti statistici e di visualizzazione di KDD
(comprese le reti neurali e la programmazione a logica induttiva)
- Mining in-the-large vs Mining in-the-small
- Gestione del rumore
- Problemi di sicurezza e privacy in KDD
- Applicazioni KDD innovative/di successo in ambito scientifico, governativo,
Commercio e industria.

Sono richiesti sia documenti di ricerca che applicativi. Tutti inviati
i documenti saranno rivisti sulla base della qualità tecnica, della pertinenza
a KDD, significato e chiarezza. I paper accettati saranno pubblicati
negli atti del convegno di un editore internazionale. UN
il numero selezionato dei documenti accettati sarà ampliato e rivisto
per l'inserimento in un numero speciale di una rivista internazionale.

Tutti gli invii devono essere limitati a un massimo di 5.000 parole. quattro
le copie cartacee devono essere inoltrate al seguente indirizzo.

Professor Ramamohanarao Kotagiri (PAKDD '98)
Dipartimento di Informatica
L'Università di Melbourne
Parkville, VIC 3052
Australia

Si prega di includere una copertina contenente il titolo, gli autori (nomi,
indirizzi postali ed e-mail), un abstract di 200 parole e fino a 5
parole chiave. Questa pagina di copertina deve accompagnare la carta.

*************** Appuntamenti importanti ***************
* 4 copie degli elaborati completi ricevute entro: 16 ottobre 1997 *
* avvisi di accettazione: 22 dicembre 1997 *
* fotocamera pronta entro il: 30 gennaio 1998 *
*************************************************************

Ross Quinlan Sydney University
Bala Srinivasan Monash Universityash

Xindong Wu Monash University
Ramamohanarao Kotagiri Melbourne University

Kevin Korb Monash University
Graham Williams CSIRO, Australia

Università Lipo Wang Deakin

Jon Oliver Monash University

Michelle Riseley Monash University

Grigoris Antoniou James Boyce Ivan Bratko
Mike Cameron-Jones Arbee Chen David Cheung
Vic Ciesielski Honghua Dai John Debenham
Olivier de Vel Tharam Dillon Guozhu Dong
Peter Eklund Usama Fayyad Matjaz Gams
Yike Guo David Hand Evan Harris
David Heckerman David Kemp Masaru Kitsuregawa
Kevin Korb Hingyan Lee Jae-Kyu Lee
Deyi Li Bing Liu Huan Liu
Zhi-Qiang Liu Hongjun Lu Dickson Lukose
Kia Makki Heikki Mannila Peter Milne
Shinichi Morishita Hiroshi Motoda Hwee-Leng Ong
Jon Oliver Maria Orlowska G. Piatetsky-Shapiro
Niki Pissinou Peter Ross Claude Sammut
S. Seshadri Hayri Sever Arun Sharma
Heinz Schmidt Evangelos Simoudis Atsuhiro Takasu
Takao Terano B. Thuraisingham Kai Ming Ting
David Urpani R. Uthurusamy Lipo Wang
Geoff Webb Graham Williams ha battuto Wuthrich
Xin Yao John Zeleznikow Dian-cheng Zhang
Ming Zhao Zijian Zheng Ning Zhong
Justin Zobel

Il dottor Xindong Wu
Dipartimento di sviluppo software
Università di Monash
900 Dandenong Road
Caulfield East, Melbourne 3145
Australia

Telefono: +61 3 9903 1025
Fax: +61 3 9903 1077
E-mail: [email protected]

Precedente 8 Successivo Inizio Data: mar, 6 maggio 1997 13:08:00 -0500 (EST)
Da: 'David Leake' ([email protected])
Oggetto: ICCBR-97: Primo invito a partecipare

ICCBR-97
Seconda conferenza internazionale sul ragionamento basato sui casi

Brown University
Providence, Rhode Island, 25-27 luglio 1997

Nel 1995, la prima Conferenza Internazionale sul Ragionamento Basato su Casi (ICCBR-95)
si è tenuto a Sesimbra, in Portogallo, come inizio di una serie biennale. ICCBR-97,
la Seconda Conferenza Internazionale sul Ragionamento Basato su Casi, si terrà presso
Brown University a Providence, Rhode Island, il 25-27 luglio, subito prima
a AAAI-97 e IAAI-97.

Il programma dell'ICCBR-97 includerà sia la ricerca che le applicazioni. Il
la conferenza di tre giorni comprenderà conferenze su invito, sessioni di documenti e poster,
e pannelli che presentano sia lavori maturi che nuove idee, selezionati tra oltre
100 iscrizioni alla conferenza. La conferenza mira a raggiungere un
vivace interscambio tra ricercatori e professionisti con differenti
prospettive su questioni fondamentalmente connesse, al fine di esaminare e
avanzare lo stato dell'arte nel ragionamento basato sui casi e nei campi correlati.

Gli argomenti che verranno affrontati nelle presentazioni della conferenza includono:

* Rappresentazione del caso, indicizzazione e recupero, valutazione della somiglianza, caso
adattamento e ragionamento analogico
* Apprendimento basato su casi e istanze, apprendimento degli indici e integrazione
CBR con altri metodi di apprendimento
* Ragionamento basato su casi e approcci correlati per aree di attività come
educazione, design e medicina
* Integrazione di CBR con altri metodi di intelligenza artificiale e confronti con altri
approcci
* Metodi e sistemi per il supporto alle decisioni, la gestione della conoscenza e
recupero intelligente delle informazioni
* Nuove aree applicative per tecniche basate su casi, applicazioni distribuite
con un impatto significativo e lezioni apprese dall'applicazione
sviluppo

10-13 novembre 1997
International Plaza Hotel
Mississauga, Ontario, Canada

Quest'anno, stiamo sollecitando documenti su una vasta gamma di argomenti, tra cui =
ma non limitato a quanto segue:

- Sistemi e applicazioni distribuiti: Internet e WWW, elettronici
commercio, teleapprendimento, telemedicina, CSCW, multimediale, distribuito
tecnologie a oggetti, Java, analisi delle prestazioni, reti ad alta velocità,
e gestione delle applicazioni

- Tecnologia dei database: data mining, recupero della conoscenza, digitale =
biblioteche e data warehousing

- Tecnologie utente: interazione uomo-computer, navigazione e GUI

- Ingegneria e pratiche del software: manutenzione, ripristino del progetto, programma
comprensione, visualizzazione, riutilizzo, strutture e modelli di progettazione,
ambienti di sviluppo, affidabilità, test e validazione,
metriche e sistemi in tempo reale

- Tecnologia del compilatore: nuove tecniche, sviluppo del compilatore, ottimizzazione,
parallelismo e architetture

Attendiamo con impazienza la vostra partecipazione.

Dott. Hakan Erdogmus
Co-presidente del programma CASCON'97
[email protected]

Ci saranno 36 documenti lunghi, 33 brevi e 15 poster al secondo annuale
Conferenza sulla programmazione genetica che si terrà a luglio
13-16 (domenica - mercoledì), 1997 alla Stanford University.
Inoltre, ci saranno documenti dell'ultima ora (pubblicati in un separato
prenotare a metà giugno dopo la scadenza dell'11 giugno per gli ultimi lavori).
Gli argomenti includono, ma non sono limitati a,
applicazioni della programmazione genetica, fondamenti teorici di
programmazione genetica, problemi di implementazione, estensioni tecniche, cellulare
codifica, hardware evolutivo, programmi in linguaggio macchina evolutivi, automatizzato
evoluzione dell'architettura dei programmi, evoluzione e uso di modelli mentali,
programmazione automatica di strategie multi-agente, artificiale distribuito
intelligenza, autoparallelizzazione di algoritmi, sintesi di circuiti automatizzati,
programmazione automatica di automi cellulari, induzione, identificazione del sistema,
controllo, progettazione automatizzata, compressione di dati e immagini, analisi delle immagini, pattern
riconoscimento, applicazioni di biologia molecolare, induzione grammaticale e
parallelizzazione. Sono inoltre richiesti documenti che descrivono i recenti sviluppi in
le seguenti aree aggiuntive: algoritmi genetici, sistemi di classificazione,
programmazione evolutiva e strategie di evoluzione, vita artificiale e
robotica evolutiva, calcolo del DNA e hardware evolutivo.
-----------------------------------------------------------------------


Contenuti

La teoria degli automi astratti è stata sviluppata a metà del XX secolo in relazione agli automi finiti. [1] La teoria degli automi era inizialmente considerata una branca della teoria dei sistemi matematici, che studiava il comportamento dei sistemi a parametri discreti. I primi lavori sulla teoria degli automi differivano dai lavori precedenti sui sistemi utilizzando l'algebra astratta per descrivere i sistemi di informazione piuttosto che il calcolo differenziale per descrivere i sistemi materiali. [2] La teoria del trasduttore a stati finiti è stata sviluppata con nomi diversi da diverse comunità di ricerca. [3] Il concetto precedente di macchine di Turing è stato incluso nella disciplina insieme a nuove forme di automi a stato infinito, come gli automi pushdown.

Il 1956 vide la pubblicazione di Studi sugli automi, che ha raccolto il lavoro di scienziati tra cui Claude Shannon, W. Ross Ashby, John von Neumann, Marvin Minsky, Edward F. Moore e Stephen Cole Kleene. [4] Con la pubblicazione di questo volume, "la teoria degli automi è emersa come disciplina relativamente autonoma". [5] Il libro includeva la descrizione di Kleene dell'insieme di eventi regolari, o linguaggi regolari, e una misura relativamente stabile della complessità nei programmi della macchina di Turing di Shannon. [6] Nello stesso anno, Noam Chomsky descrisse la gerarchia di Chomsky, una corrispondenza tra automi e grammatiche formali, [7] e Ross Ashby pubblicò Introduzione alla cibernetica, un libro di testo accessibile che spiega gli automi e le informazioni utilizzando la teoria degli insiemi di base.

Lo studio degli automi lineari ha portato al teorema di Myhill-Nerode, [8] che fornisce una condizione necessaria e sufficiente affinché un linguaggio formale sia regolare e un conteggio esatto del numero di stati in una macchina minima per il linguaggio. Il pumping lemma per i linguaggi regolari, utile anche nelle prove di regolarità, è stato dimostrato in questo periodo da Michael O. Rabin e Dana Scott, insieme all'equivalenza computazionale di automi finiti deterministici e non deterministici. [9]

Negli anni '60 emerse un insieme di risultati algebrici noti come "teoria della struttura" o "teoria della decomposizione algebrica", che riguardava la realizzazione di macchine sequenziali da macchine più piccole mediante interconnessione. [10] Mentre qualsiasi automa finito può essere simulato utilizzando un insieme di porte universali, ciò richiede che il circuito di simulazione contenga anelli di complessità arbitraria. La teoria della struttura si occupa della realizzabilità "senza loop" delle macchine. [5] Negli anni '60 prese forma anche la teoria della complessità computazionale. [11] [12] Entro la fine del decennio, la teoria degli automi venne vista come "la pura matematica dell'informatica". [5]

Quella che segue è una definizione generale di automa, che limita una definizione più ampia di sistema a quella vista come agente in passi temporali discreti, con il suo comportamento di stato e le sue uscite definite ad ogni passo da funzioni immutabili solo del suo stato e ingresso. [5]

Descrizione informale Modifica

Un automa corre quando viene data una sequenza di ingressi in discreto (individuale) passi temporali o passaggi. Un automa elabora un input scelto da un insieme di simboli o lettere, che si chiama an inserire l'alfabeto. I simboli ricevuti dall'automa come input ad ogni passo sono una sequenza di simboli chiamata parole. Un automa ha un insieme di stati. In ogni momento durante una corsa dell'automa, l'automa è in uno dei suoi stati. Quando l'automa riceve un nuovo input si sposta in un altro stato (o transizioni) basato su a funzione di transizione che prende come parametri lo stato precedente e il simbolo di input corrente. Allo stesso tempo, un'altra funzione chiamata funzione di uscita produce simboli dal alfabeto in uscita, anche in base allo stato precedente e al simbolo di ingresso corrente. L'automa legge i simboli della parola di ingresso e le transizioni tra gli stati fino a quando la parola non viene letta completamente, se è di lunghezza finita, a quel punto l'automa si ferma. Uno stato in cui l'automa si ferma è chiamato stato finale.

Per investigare le possibili sequenze stato/input/output in un automa usando la teoria del linguaggio formale, a una macchina può essere assegnato un stato di partenza e un set di stati accettanti. Quindi, a seconda che una corsa che parte dallo stato iniziale termini in uno stato accettante, si può dire che l'automa accettare o rifiutare una sequenza di input. L'insieme di tutte le parole accettate da un automa si chiama lingua riconosciuta dall'automa. Un esempio familiare di una macchina che riconosce una lingua è una serratura elettronica che accetta o rifiuta i tentativi di inserire il codice corretto.

Definizione formale Modifica

Gli automi sono definiti per studiare macchine utili sotto formalismo matematico. Quindi, la definizione di un automa è aperta a variazioni secondo la "macchina del mondo reale", che vogliamo modellare usando l'automa. Le persone hanno studiato molte varianti di automi. Di seguito sono riportate alcune varianti popolari nella definizione dei diversi componenti degli automi.

  • Ingresso finito: Un automa che accetta solo una sequenza finita di simboli. La definizione introduttiva di cui sopra comprende solo parole finite.
  • Ingresso infinito: Un automa che accetta infinite parole (ω-words). Tali automi sono chiamati -automi.
  • Inserimento di parole ad albero: L'ingresso può essere a albero dei simboli invece della sequenza di simboli. In questo caso dopo aver letto ogni simbolo, l'automa legge tutti i simboli successori nell'albero di input. Si dice che l'automa fa una copia di per sé per ogni successore e ciascuna di tali copie inizia a funzionare su uno dei simboli successori dallo stato secondo la relazione di transizione dell'automa. Un tale automa è chiamato automa ad albero.
  • Ingresso albero infinito : Le due estensioni sopra possono essere combinate, quindi l'automa legge una struttura ad albero con rami (in)finiti. Un tale automa è chiamato automa ad albero infinito
  • Stato singolo: Un automa con uno stato, chiamato anche a circuito combinatorio, esegue una trasformazione che può implementare la logica combinatoria. [10]
  • stati finiti: Un automa che contiene solo un numero finito di stati.
  • Stati infiniti: Un automa che potrebbe non avere un numero finito di stati, o anche un numero numerabile di stati. Diversi tipi di memoria astratta possono essere usati per dare a tali macchine descrizioni finite.
  • Stack di memoria: Un automa può anche contenere della memoria extra sotto forma di una pila in cui i simboli possono essere inseriti e estratti. Questo tipo di automa è chiamato a automa pushdown
  • Memoria di coda: Un automa può avere memoria sotto forma di coda. Tale macchina è chiamata macchina della coda ed è Turing-completo.
  • Memoria su nastro: Gli input e gli output degli automi sono spesso descritti come input e output nastri. Alcune macchine hanno ulteriori nastri funzionanti, tra cui la macchina di Turing, l'automa lineare limitato e il trasduttore logaritmico.
  • Deterministico: Per un dato stato corrente e un simbolo di input, se un automa può saltare solo a uno e solo uno stato, allora è un automa deterministico.
  • non deterministico: Un automa che, dopo aver letto un simbolo di input, può saltare in uno qualsiasi di un numero di stati, come consentito dalla sua relazione di transizione. Si noti che il termine funzione di transizione è sostituito dalla relazione di transizione: L'automa in modo non deterministico decide di saltare in una delle scelte consentite. Tali automi sono chiamati automi non deterministici.
  • Alternanza: Questa idea è abbastanza simile all'automa ad albero ma ortogonale. L'automa può eseguire il suo più copie sul stesso simbolo di lettura successiva. Tali automi sono chiamati automi alternati. La condizione di accettazione deve soddisfare tutte le esecuzioni di tale copie per accettare l'input.
  • Accettazione di parole finite: Come descritto nella definizione informale di cui sopra.
  • Accettazione di infinite parole: un automa omega non può avere stati finali, poiché le parole infinite non terminano mai. Piuttosto, l'accettazione della parola viene decisa osservando la sequenza infinita di stati visitati durante la corsa.
  • Accettazione probabilistica: Un automa non deve accettare o rifiutare rigorosamente un input. Può accettare l'input con una probabilità compresa tra zero e uno. Ad esempio, l'automa quantistico finito, l'automa geometrico e l'automa metrico hanno un'accettazione probabilistica.

Diverse combinazioni delle variazioni di cui sopra producono molte classi di automi.

La teoria degli automi è una materia che studia le proprietà di vari tipi di automi. Ad esempio, vengono studiate le seguenti domande su un dato tipo di automi.

  • Quale classe di linguaggi formali è riconoscibile da qualche tipo di automi? (Lingue riconoscibili)
  • Sono certi automi? Chiuso sotto unione, intersezione o complementazione di linguaggi formali? (Proprietà di chiusura)
  • Quanto è espressivo un tipo di automa in termini di riconoscimento di una classe di linguaggi formali? E il loro relativo potere espressivo? (Gerarchia linguistica)

La teoria degli automi studia anche l'esistenza o l'inesistenza di algoritmi efficaci per risolvere problemi simili al seguente elenco:

  • Un automa accetta qualsiasi parola di input? (Controllo del vuoto)
  • È possibile trasformare un dato automa non deterministico in un automa deterministico senza cambiare il linguaggio riconoscibile? (Determinazione)
  • Per un dato linguaggio formale, qual è il più piccolo automa che lo riconosce? (Minimizzazione)

Quello che segue è un elenco incompleto di tipi di automi.

Automa Lingua riconoscibile
Macchina a stati finiti (FSM) non deterministica/deterministica lingue regolari
Automa pushdown deterministico (DPDA) linguaggi deterministici liberi dal contesto
Automa pushdown (PDA) linguaggi senza contesto
Automa lineare limitato (LBA) linguaggi sensibili al contesto
macchina di Turing linguaggi ricorsivamente enumerabili
Automa deterministico Büchichi -limite lingue
Automa Büchi non deterministico -lingue regolari
Automa di Rabin, automa di Streett, automa di parità, automa di Muller

Automi discreti, continui e ibridi Modifica

Normalmente la teoria degli automi descrive gli stati delle macchine astratte, ma esistono automi discreti, automi analogici o automi continui o automi ibridi discreti-continui, che utilizzano rispettivamente dati digitali, dati analogici o tempo continuo o dati digitali e analogici.

Quella che segue è una gerarchia incompleta in termini di poteri di diversi tipi di macchine virtuali. La gerarchia riflette le categorie nidificate di linguaggi che le macchine sono in grado di accettare. [14]

Ogni modello nella teoria degli automi svolge ruoli importanti in diverse aree applicate. Gli automi finiti sono usati nell'elaborazione del testo, nei compilatori e nella progettazione dell'hardware. La grammatica libera dal contesto (CFG) viene utilizzata nei linguaggi di programmazione e nell'intelligenza artificiale. In origine, i CFG venivano utilizzati nello studio delle lingue umane. Gli automi cellulari sono usati nel campo della vita artificiale, l'esempio più famoso è Game of Life di John Conway. Alcuni altri esempi che potrebbero essere spiegati utilizzando la teoria degli automi in biologia includono i modelli di crescita e pigmentazione dei molluschi e delle pigne. Andando oltre, alcuni scienziati sostengono una teoria che suggerisce che l'intero universo sia calcolato da una sorta di automa discreto. L'idea è nata nel lavoro di Konrad Zuse ed è stata resa popolare in America da Edward Fredkin. Gli automi compaiono anche nella teoria dei campi finiti: l'insieme dei polinomi irriducibili che possono essere scritti come composizione di polinomi di secondo grado è infatti un linguaggio regolare. [15] Un altro problema per il quale si possono usare gli automi è l'induzione di linguaggi regolari.

I simulatori di automi sono strumenti pedagogici utilizzati per insegnare, apprendere e ricercare la teoria degli automi. Un simulatore di automi prende come input la descrizione di un automa e quindi simula il suo funzionamento per una stringa di input arbitraria. La descrizione dell'automa può essere inserita in diversi modi. Un automa può essere definito in un linguaggio simbolico o la sua specifica può essere inserita in una forma prestabilita o il suo diagramma di transizione può essere disegnato facendo clic e trascinando il mouse. I ben noti simulatori di automi includono Turing's World, JFLAP, VAS, TAGS e SimStudio. [16]

Si possono definire diverse categorie distinte di automi [17] seguendo la classificazione degli automi in diversi tipi descritti nella sezione precedente. La categoria matematica di automi deterministici, macchine sequenziali o automi sequenziali, e le macchine di Turing con omomorfismi di automi che definiscono le frecce tra gli automi sono una categoria cartesiana chiusa, [18] [19] ha sia limiti categoriali che colimiti. Un omomorfismo di automi mappa un quintuplo di un automa UNio sul quintuplo di un altro automa UNJ. [20] Gli omomorfismi di automi possono anche essere considerati come trasformazioni di automi o come omomorfismi di semigruppi, quando lo spazio degli stati, S, dell'automa è definito come un semigruppo SG. I monoidi sono anche considerati un'impostazione adatta per gli automi nelle categorie monoidali. [21] [22] [23]

Categorie di automi variabili

Si potrebbe anche definire a automa variabile, nel senso di Norbert Wiener nel suo libro su L'uso umano degli esseri umani attraverso gli endomorfismi A i → A i a A_> . Quindi, si può dimostrare che tali omomorfismi di automi variabili formano un gruppo matematico. Nel caso di automi non deterministici o di altri tipi complessi, quest'ultimo insieme di endomorfismi può diventare, tuttavia, un gruppoide dell'automa variabile. Pertanto, nel caso più generale, le categorie di automi variabili di qualsiasi tipo sono categorie di gruppoidi o categorie di gruppoidi. Inoltre, la categoria degli automi reversibili è quindi una 2-categoria, e anche una sottocategoria della 2-categoria dei gruppoidi, o la categoria dei gruppoidi.


Contenuti

Nell'ambito del MCA avvicinarsi a un oggetto in fase di modellazione è considerato come un insieme di elementi/automi interagenti. Le dinamiche dell'insieme degli automi sono definite dalle loro forze reciproche e dalle regole per le loro relazioni. Questo sistema esiste e opera nel tempo e nello spazio. La sua evoluzione nel tempo e nello spazio è governata dalle equazioni del moto. Le forze reciproche e le regole per le relazioni tra elementi sono definite dalla funzione della risposta dell'automa. Questa funzione deve essere specificata per ogni automa. A causa della mobilità degli automi, devono essere presi in considerazione i seguenti nuovi parametri degli automi cellulari: R io – raggio-vettore dell'automa V io – velocità dell'automa io – velocità di rotazione dell'automa io – vettore di rotazione dell'automa io sono – massa dell'automa J io – momento d'inerzia dell'automa.

Il nuovo concetto del metodo MCA si basa sull'introduzione del stato della coppia di automi (relazione di coppie interagenti di automi) oltre a quello convenzionale - lo stato di un automa separato. Si noti che l'introduzione di questa definizione permette di passare dal concetto di rete statica al concetto di vicini. Di conseguenza, gli automi hanno la capacità di cambiare i loro vicini cambiando gli stati (relazioni) delle coppie.

L'introduzione di un nuovo tipo di stati porta a nuovi parametri da utilizzare come criteri per cambiare le relazioni. È definito come un automa che si sovrappone ai parametri ciao ij . Quindi la relazione degli automi cellulari è caratterizzata dal valore del loro sovrapposizione.

La struttura iniziale è formata stabilendo determinate relazioni tra ciascuna coppia di elementi vicini.

In contrasto con il metodo classico dell'automa cellulare nel metodo MCA non solo un singolo automa ma anche a la relazione della coppia di automi può essere cambiata. Secondo il concetto di automi bistabili ci sono due tipi di stati di coppia (relazioni):

collegato – entrambi gli automi appartengono a un solido
scollegato – ogni automa della coppia appartiene a diversi corpi o parti di corpo danneggiate.

Così la cambiamento dello stato delle relazioni di coppia è controllato dai movimenti relativi degli automi e i mezzi formati da tali coppie possono essere considerati mezzi bistabili.

L'evoluzione dei media MCA è descritta da quanto segue equazioni del moto per la traslazione:

A causa della dimensione finita degli automi mobili, gli effetti di rotazione devono essere presi in considerazione. Il equazioni del moto per la rotazione può essere scritto come segue:

Qui Θ ij è l'angolo di rotazione relativa (è un parametro di commutazione come h ij per la traslazione), q ij è la distanza dal centro dell'automa io al punto di contatto dell'automa J (braccio del momento), τ ij è l'interazione tangenziale della coppia, S ( ij , ik ) è un certo coefficiente associato al trasferimento del parametro Θ da una coppia all'altra (è simile a C ( ij , ik ) dall'equazione per la traduzione).

Queste equazioni sono del tutto simili alle equazioni del moto per l'approccio a molte particelle.

Traduzione della coppia automi Il parametro di deformazione adimensionale per la traslazione del io j La coppia di automi può essere presentata come:

ε io j = h io j r 0 io j = ( q io j + q j i ) − ( d io + d j ) / 2 ( d io + d j ) / 2 = <>over r_<0>^>=+q^ ight)-left(d^+d^ ight)<ig />2 over left(d^+d^ ight)<ig />2>>

dove t passo temporale, Vn ij – velocità relativa.

La rotazione della coppia di automi può essere calcolata per analogia con le ultime relazioni di traslazione.

Il ij il parametro viene utilizzato come misura della deformazione dell'automa io sotto la sua interazione con l'automa J. In cui si q ij – è una distanza dal centro dell'automa io al suo punto di contatto con l'automa J R io = d io /2 (d io – è la dimensione dell'automa io).

Come esempio si considera il provino in titanio sottoposto a carico ciclico (tensione – compressione). Il diagramma di carico è mostrato nella figura seguente:

Schema di caricamento Diagramma di caricamento
(Segni rossi sono i dati sperimentali)

A causa della mobilità di ciascun automa, il metodo MCA consente di prendere in considerazione direttamente azioni come:

  • miscelazione di massa
  • effetti di penetrazione
  • reazioni chimiche
  • deformazione intensiva
  • trasformazioni di fase
  • cumulo di danni
  • frammentazione e frattura
  • generazione e sviluppo di crepe

Utilizzando condizioni al contorno di diverso tipo (fisse, elastiche, viscoelastiche, ecc.) è possibile imitare diverse proprietà del mezzo circostante, contenente il sistema simulato. È possibile modellare diverse modalità di carico meccanico (tensione, compressione, deformazione di taglio, ecc.) impostando condizioni aggiuntive ai confini.


Automi cellulari

Gli automi cellulari sono simulazioni su una griglia lineare, quadrata o cubica in cui ogni cella può trovarsi in un singolo stato, spesso solo ON e OFF, e in cui ogni cella opera da sola, prendendo in input gli stati dei suoi vicini e mostrando un stato come output.

Uno degli esempi più semplici sarebbe un automa cellulare unidimensionale in cui ogni cellula ha due stati, ON e OFF, che sono rappresentati da bianco e nero, e dove ogni cellula si accende se almeno uno dei suoi vicini è in lo stato ON. Quando viene avviato da 1 cella, questo crea semplicemente una linea nera più ampia. Quando i livelli vengono mostrati tutti in una volta, però, puoi vedere che ha una forma piramidale.

Ad esempio, nella figura sopra, la seconda riga viene generata dall'esecuzione della regola per tutte le celle nella prima riga, la terza riga dalla seconda riga e così via. Figure più complicate possono essere generate da regole diverse, come un automa cellulare in cui una cella cambia in ON se la cella in alto a sinistra o in alto a destra è ON, ma non se entrambe sono attive. Questo crea un triangolo di Sierpinski quando si parte da una singola cella:

Stephen Wolfram ha sviluppato un sistema di numerazione per tutti gli automi cellulari che si basano solo su se stessi, il loro vicino di sinistra e il loro vicino di destra, spesso chiamati automi cellulari elementari, che assomiglia a questo per gli automi del triangolo di Sierpinski (Regola 18) :

Questo codice ha tutti i possibili stati ON e OFF per tre celle in alto e l'effetto che crea sulla cella sottostante in basso. Usando questo sistema, possiamo scoprire che ci sono 256 diversi automi cellulari elementari. Possiamo anche creare facilmente un numero per ogni automa semplicemente convertendo gli stati ON e OFF in basso in 1 e 0, e quindi combinandoli per creare un numero binario (00010010 nell'esempio del triangolo di Sierpinski). Quindi, convertiamo il binario in decimale e quindi otteniamo il numero della regola. (128*0+64*0+32*0+16*1+8*0+4*0+2*1+1*0= 18 per l'esempio). Possiamo anche fare il contrario per ottenere un automa cellulare da un numero. Usando questo metodo, possiamo creare immagini di tutti i 255 automi cellulari elementari:

Alcuni di questi sono piuttosto interessanti, come la Regola 30 e la Regola 110:

Mentre alcuni sono piuttosto noiosi, come la Regola 0, che è solo bianca, o la Regola 14, che è una singola linea diagonale.

Ci sono molte variazioni su questo tipo di automi cellulari di base, come un'estensione del codice in cui sono inclusi anche i vicini più prossimi. Ciò si traduce in 4294967296 diversi automi cellulari, alcuni dei quali sembrano creare modelli quasi tridimensionali come gli automi cellulari 3D Tetrahedrons (regola 3283936144) che sembrano mostrare alcune forme tetraedriche che spuntano da un piano.

Esistono anche automi cellulari totalitari, creati basando in qualche modo la cella successiva sulla media delle celle in alto a sinistra, al centro e in alto a destra sopra di essa. Questi possono avere più di due stati e talvolta producono modelli dall'aspetto molto strano, come la Regola 1599, un automa cellulare a 3 stati:

Oltre a tutti questi, ci sono automi cellulari a valori continui, che, invece di avere celle che possono essere solo in determinati stati, hanno le celle con valori di numeri reali. Quindi, ad ogni passaggio viene applicata una funzione alla cella che deve essere modificata e alle sue vicine. Un buon esempio di questo è l'automa cellulare Heat, in cui la funzione è ((left_neighbor+old_cell+right_neighbor)/3+ un numero compreso tra 0 e 1) mod 1). Produce un effetto “bollente”, in cui assomiglia a una pentola d'acqua che bolle lentamente su un forno.

Ci sono tonnellate di automi cellulari unidimensionali che Stephen Wolfram ha riempito la maggior parte di un intero libro (1200 pagine) con questi. Tuttavia, ci sono essenzialmente solo 4 classi di automi cellulari. Il primo tipo è il più noioso è dove gli automi cellulari si evolvono in un unico stato uniforme. Un esempio di questo sarebbe l'automa cellulare elementare Regola 254 (il primo esempio), che alla fine si evolve in tutto nero. Il secondo tipo, la ripetizione, è un po' più interessante, in quanto non evolve in un unico stato ma è invece ripetitivo. Questo può includere una singola linea, una semplice oscillazione o un comportamento simile a un frattale, un esempio dei quali sarebbe la Regola 18. Il terzo tipo è semplicemente un comportamento completamente caotico - non molto interessante, ma decisamente più dei due precedenti - come in Regola 30. L'ultimo tipo, il tipo 4, è dove ci sono molte strutture individuali che interagiscono, a volte passando attraverso, altre volte esplodendo. Un esempio di ciò potrebbe essere la Regola 110. Questo tipo è probabilmente il più interessante da guardare, poiché l'esito finale è sconosciuto.

Questi 4 tipi coprono quasi tutti gli automi cellulari, ad eccezione di quelli che sembrano essere a metà strada tra i tipi.

Possiamo facilmente andare oltre la dimensione 1 e studiare gli automi cellulari bidimensionali. Probabilmente il più famoso di questi è Game of Life di Conway, inventato da John Conway nel 1970. In esso, gruppi di cellule sembrano crescere e poi collassare mentre gli “alianti” si muovono sullo schermo. Utilizza solo 4 regole e rientra facilmente nella categoria degli automi cellulari di Classe 4.

1. Qualsiasi cellula viva con meno di 2 vicini muore. (fame)

2. Qualsiasi cellula viva con più di 3 vicini muore. (sovraffollamento)

3. Qualsiasi cellula viva con 2 o 3 vicini rimane in vita.

4. Qualsiasi cellula morta con tre vicini vivi diventa viva (nascita)

Qui, l'intorno di una cella è definito come le 8 celle che la circondano.

Quando il Gioco della Vita è stato mostrato per la prima volta, tonnellate di persone sono impazzite scrivendo programmi per simularlo sui computer, e presumibilmente migliaia di ore di tempo al computer sono state “sprecate” a simulare questi schemi. Un lavoratore di un'azienda ha persino installato un pulsante “Boss” per cambiare il display da Life a qualsiasi cosa su cui avrebbe dovuto lavorare quando il suo capo è passato! Conway aveva offerto un premio di 50 dollari a chiunque fosse riuscito a trovare uno schema che si espandesse all'infinito. Potrebbe trattarsi di una sorta di cannone a vela, che spara alianti, un pesce palla, che lascia una scia di detriti, o un riempitivo spaziale che si espande in tutte le direzioni. Il premio è stato rivendicato da Bill Gosper quando ha scoperto il Gosper Glider Gun.

Da allora, sono stati scoperti molti nuovi schemi nel Gioco della Vita, come un treno palla, un contatore esadecimale, un generatore di frattali e persino un “computer” che farà praticamente tutto ciò per cui è programmato.

Parti del computer della vita

Ci sono molti altri automi cellulari bidimensionali, che possono essere scritti in una certa notazione che dice con quali numeri vicini la cellula morta diventa viva, e per quali numeri vicini la cellula viva rimane in vita. Ad esempio, Game of Life di Conway potrebbe essere scritto come B3/S23 . Molti altri automi cellulari possono essere scritti usando questa notazione. Alcuni dei più interessanti sono l'automa di Fredkin (B1357/S02468), che replica qualsiasi schema di partenza. Questo è tutto ciò che fa, senza eccezioni, quindi non c'è alcuna possibilità di creare qualcosa di simile a un sommatore. Un'altra interessante è la regola “Maze” (B3/S12345), che produce pattern simili a labirinti. La modifica della regola in B37/S12345 crea punti che si muovono attraverso la forma. Uno dei più interessanti di questi, tuttavia, è 2ࡨ Life (B36/S125), una regola che è simile nel carattere a Life ma ha modelli molto diversi. Gli alianti sono anche un po' più rari, sebbene ci siano molti oscillatori interessanti. In regole come queste, come Day & Night (B3678/S3478) non fa quasi alcuna differenza se i colori sono invertiti. Anche Day & Night, alla fine dei pattern, ha molti oscillatori.

Naturalmente, puoi estendere questo modulo per consentire più stati. Brian’s Brain (/2/3) ne è un esempio, in cui ci sono tre stati e in cui gli alianti e i cannoni per alianti sono molto comuni. In effetti, le nature morte sono quasi inesistenti! La notazione sopra significa che una cella nello stato 1 (e solo nello stato 1) rimane in vita se ha vicini (nulli), che una cella morta diventa una cella nello stato 1 se ha 2 vicini e che ci sono 3 stati (0 ,1,2) .

Ci sono molte modifiche a questa regola, una che provoca la formazione di strutture simili a impalcature e persino una che si combina con Game of Life di Conway!

Puoi facilmente creare le tue regole semplicemente scegliendo i numeri da inserire. Molte di esse sembrano essere solo caotiche, ma puoi trovare regole che creano schemi piuttosto interessanti. Uno buono è l'automa cellulare di Star Wars, 345/2/4, che inizia come la regola del cervello di Brian, ma presto crea strutture che sparano alianti. Una cosa divertente da fare in questa regola è creare “Train track” che consentono a 1ࡩ rettangoli di muoversi intorno a loro in entrambe le direzioni. Naturalmente, puoi anche simulare tutte le regole di Life-ish modificando il numero di stati in 2, in modo che ci siano solo gli stati ON e OFF.

Come se tutto questo non bastasse, c'è anche una generalizzazione del precedente in arbitrariamente molte regole per arbitrariamente molti stati, come una tabella delle regole. Fondamentalmente, le regole si basano su una grande tabella che indica alla cella in un determinato stato di passare a uno stato diverso (o uguale) se ha <this> molti vicini attivi. Le diverse regole per ogni stato rendono facile far fare all'automa cellulare esattamente quello che vuoi che faccia. Un buon esempio di questo tipo di regola è l'automa cellulare Wireworld, inventato da Brian Silverman, in cui gli elettroni viaggiano lungo i fili simulando le connessioni in un computer. È facile creare un cancello a una via, un cancello AND, un orologio, un cancello NOT… e quasi tutto ciò di cui hai bisogno per creare un computer. In effetti, Mark Owen ha persino realizzato un computer wireworld che calcola e visualizza i numeri primi!

Incredibile quando viene effettivamente eseguito.

Rudy Rucker ha anche realizzato molti automi cellulari Rule Table, uno dei più interessanti è il suo automa cellulare Cars, che produce auto da corsa in diversi tipi, di solito non qualcosa che ti aspetteresti di vedere da un automa cellulare. Le auto si scontrano anche l'una con l'altra e, nel processo, creano auto piuttosto strane.

Ho anche realizzato un interessante automa cellulare, che utilizza solo 2 stati, ma mostra ancora un comportamento interessante su griglie avvolte, chiamato SkyscraperMakers. In esso si realizzano facilmente grandi strutture e c'è un pesce palla molto semplice che richiede solo 6 celle. Anche i segnali sembrano trasferirsi attraverso le strutture, ma per lo più si limitano ad abbassare le torri.

Esistono anche regole per gli automi cellulari in cui solo 1 cella è effettivamente attiva alla volta. Un esempio di ciò è l'automa cellulare Ant di Langton, in cui la cellula in movimento ha due regole:

1. Se ti trovi su un quadrato bianco, gira a destra, cambia il colore del quadrato da bianco a nero e vai avanti di un quadrato.

2. Se ti trovi su un quadrato nero, gira a sinistra, cambia il colore del quadrato da nero a bianco e vai avanti di un quadrato.

Sebbene questo sembri molto semplice, quando l'automa cellulare funziona su una griglia vuota, lo schema prodotto è piuttosto caotico. In effetti, devi aspettare circa 11.000 passi fino a quando “ant” produce un “highway” in cui la formica ripete lo stesso schema più e più volte.

I primi 200 passi di Ant . di Langton

Naturalmente, c'è una generalizzazione a più stati e regole diverse, in cui dici semplicemente alla formica cosa fare quando tocca un certo stato. Di solito è espresso usando una stringa di R e L per mostrare quale direzione prende la formica quando tocca una cella di un certo colore. Ad esempio, la classica regola Ant di Langton's potrebbe essere espressa come RL, il che significa che gira a destra quando tocca una cella di stato 0 (bianco) e gira a sinistra quando tocca una cella di stato 1. Usando questa generalizzazione, c'è sono alcuni automi cellulari piuttosto interessanti. Ad esempio, LLRR crea una forma cardiode:

Mentre una delle regole più lunghe, LRRRRRLLR riempie lo spazio intorno a sé in un quadrato.

Naturalmente, l'infinità di automi cellulari uni e bidimensionali non era abbastanza per alcune persone, che sono passate agli automi cellulari tridimensionali. La notazione per questi è simile alla normale notazione Life (cioè, B (qualcosa)/S (qualcosa)), tranne per il fatto che i numeri vanno da 0 a 26 invece che da 0 a 8. Ci sono alcuni interessanti analoghi degli automi cellulari 2d , come il cervello di Brian, che sono stati scoperti (B4/S):

Oltre ad alcune nuove regole, come la regola “Nuvole” (B13,14,17,18,19 /S13,14,15,16,17,18,19,20,21,22,23,24 ) in cui modelli casuali formano rapidamente blob e ponti simili a nuvole tra i blob.Le “nuvole” alla fine si riducono, a volte fino a diventare nulla, ma a volte formando oscillatori piuttosto semplici:

C'è stata anche una versione di Life in 3D, tuttavia, si rivolge a semplici oscillatori molto rapidamente. Presumibilmente, si possono formare alianti, ma non ne ho visti.

Il problema con gli automi cellulari 3D, tuttavia, è che gli schermi dei computer sono bidimensionali. Quando lo schermo di un computer visualizza l'immagine di un automa cellulare 3D, la parte anteriore (che vediamo) potrebbe essere piuttosto opaca, mentre l'altra parte potrebbe essere molto caotica, ma non sapremmo la differenza. Inoltre, potrebbe esserci molta azione all'interno di un blob, ma non possiamo vedere cosa sta succedendo all'interno.

Un modo interessante per creare una forma tridimensionale da un automa cellulare è semplicemente impilare tutti gli stadi di un automa cellulare bidimensionale uno sopra l'altro. Questo fa sembrare l'automa cellulare un po' diverso. Modelli come la pistola Gosper Glider in Game of Life di Conway si trasformano in una torre con cavi di sospensione su un lato, Ant di Langton in un grattacielo simile a Sears Tower e Brain di Brian Non voglio nemmeno pensare . È piuttosto divertente costruirli da blocchi (in particolare quelli che possono essere uniti insieme), poiché i risultati sono spesso sorprendenti.

Parte del libro di Wolfram è stata dedicata alla progettazione e alla ricerca di alcuni automi cellulari che possono fare nulla– calcola che cos'è 2+2, emula altri automi cellulari, anche visualizzando lettere, chiamati automi cellulari universali. Il più semplice di questi da mostrare universale sarebbe Game of Life di Conway, creando porte AND, porte OR, una cella di memoria, un riflettore a 90 gradi e una porta NOT. Molti di questi si basano sul colpire gli alianti insieme per formare determinati risultati, e il NOT gate è quello difficile: ha bisogno di usare una pistola per alianti, o qualcosa per inviare gli alianti, per essere effettivamente un NOT gate. Una volta fatto, il resto è semplice.

Un metodo simile può essere utilizzato per dimostrare che WireWorld è universale: realizzando i componenti logici necessari, è possibile realizzare facilmente vari computer, come la calcolatrice per numeri primi di Mark Owen. Ci sono persino costruzioni realizzate mettendo insieme porte logiche in modo tale da poter realizzare automi cellulari unidimensionali!

Von Neumann progettò anche un automa cellulare bidimensionale, il cui unico scopo era dimostrare che i computer erano possibili negli automi cellulari. Le regole sono piuttosto complesse, operano principalmente su segnali che passano attraverso cavi e celle di scrittura, e l'automa cellulare ha ben 29 stati. I replicatori sono possibili, ma usano enormi “nastri” per memorizzare come dovrebbe essere costruita la struttura.

Ora ecco la parte sorprendente: anche gli automi cellulari unidimensionali possono essere universali. In particolare, Wolfram ha mostrato un certo automa cellulare prossimo più vicino a 19 stati che, data la giusta configurazione, emulerà qualsiasi altro automa cellulare unidimensionale su una base enorme (20 cellule per cellula). Di seguito sono riportati alcuni esempi di emulazione di automi cellulari:

Regola 90 e Regola 30, emulate

In particolare, sebbene sia difficile da vedere, l'automa cellulare a 19 stati emula rispettivamente la regola 90 e la regola 30.

La cosa più sorprendente, tuttavia, è che, sebbene sia tutt'altro che semplice da dimostrare, la Regola 110 è un automa cellulare universale. Ciò è stato fatto mostrando come potrebbe emulare un'altra classe di automi cellulari unidimensionali, il sistema di tag ciclico, e lavorando da lì. Alla fine, Wolfram lo mostra emulare altri automi cellulari elementari, calcolare e persino emulare macchine di Turing.

Esistono molti programmi di automi cellulari (molti di loro sono elencati su http://cafaq.com/soft/index.php), quindi elencherò semplicemente alcuni dei migliori che ho trovato.

Uno dei miei programmi preferiti è Cellebration (MCell) di Mirek, realizzato da Mirek Wojtowicz, che ha molte regole di automi cellulari (oltre 200) e ancora più modelli di automi cellulari. Ha un ampio database di modelli di vita, oltre a permetterti di creare le tue regole e salvarle facilmente. Probabilmente gli unici problemi con questo sono che la velocità dell'automa può variare a seconda del numero di celle di vita sulla scheda e che il software non è più sviluppato. Tuttavia, puoi aggiungere piccole estensioni e persino modificare il codice sorgente della versione Java online. Puoi scaricarlo qui o vedere l'implementazione di Java.

Un altro programma per simulare automi cellulari è Five Cellular Automata, che simula esattamente 5 tipi di automi cellulari: Una piccola generalizzazione della vita, utilizzando 4 parametri e q afferma La reazione di Belousov-Zhabotinsky, come un automa cellulare un automa cellulare in cui macchie di colori cercare di incontrarsi e alla fine prendere il controllo di un automa cellulare probabilistico in cui i "virus" esplodono tra la popolazione, uccidono tutti e alla fine muoiono mentre la popolazione ricresce e, infine, un modello DLA. Il programma simula abbastanza bene tutti e 5, ma fa solo quei 5 e non ci sono funzionalità di modifica manuale. Questo fa sì che il programma sia buono per la visione, ma non utile per qualsiasi sperimentazione. È possibile scaricarlo dal sito Web di Hermetic Systems.

Il migliore di questi su cui si sta sviluppando sarebbe facilmente Golly, un programma di automi cellulari che ha universi infiniti, utilizza il veloce algoritmo Hashlife di Bill Gosper, ha centinaia di modelli, inclusi alcuni lessici di Life, ed è persino scriptabile (con esempi !) sia in Python che in Perl. E legge praticamente tutti i file CA mai creati. L'unico problema è che regole completamente nuove, come creare un automa cellulare con tabella delle regole, non è molto facile a meno che non sia un automa cellulare realistico (B qualcosa/S qualcosa). Puoi scaricarlo dalla pagina Sourceforge del progetto.

Infine, c'è CAPOW di Rudy Rucker, un programma per la generazione di automi cellulari a valori continui. Supporta regole 1D e 2D, nonché una serie di automi cellulari a valori discreti. Ha anche una modalità in cui gli automi cellulari 2D vengono estrusi, in base allo stato in cui si trova la cella, in una griglia 3D. Ha molti automi cellulari, può crearne di nuovi e include uno screensaver che mostra l'animazione di vari automi cellulari. L'unico aspetto negativo è che è un po' complicato creare regole diverse o creare nuove classi CA. Puoi scaricarlo dal sito web di Rudy Rucker.

Ci sono molti più automi cellulari che non sono stati studiati, quindi il campo degli automi cellulari è ancora un campo interessante da esplorare e trovare nuove e interessanti regole.


Risultati impressionanti.
Hai una spiegazione intuitiva del perché questa particolare costruzione di automi cellulari tenda a produrre solizioni con interazioni stabili?

Sembra che i solitoni stabili tendano a formarsi abbastanza spesso quando c'è una funzione di crescita forte (ampia gamma) proveniente da un piccolo quartiere, in congiunzione con un quartiere più grande (spesso un anello, piuttosto che un cerchio solido) che fornisce una funzione di morte i ‘valori inferiori’ dell'intervallo

Molto bello. Quindi ho capito: se sono soddisfatte più condizioni “if” (per i più quartieri) è solo l'ultimo elencato nel tuo programma che conta? E se non vengono soddisfatte condizioni, ad esempio nel tuo primo esempio con più quartieri, se avg[0] e avg[1] sono entrambi 0,3, un valore che non rispetta tutte le condizioni elencate?

Per MNCA che utilizzano aggiornamenti che impostano il valore di output (come i modelli discreti), l'ultimo aggiornamento che interessa il pixel sovrascrive eventuali aggiornamenti precedenti e tale valore viene utilizzato come output.

Per l'MNCA continuo in cui vengono utilizzati gli aggiornamenti di incremento/decremento, come output viene utilizzata la somma delle modifiche totali per tutti gli aggiornamenti.

Prima che vengano applicati gli aggiornamenti, il valore di output viene impostato sul valore ‘reference’ per quel pixel. Se nessun aggiornamento influisce su quel pixel, questo valore ‘default’ verrà trasferito all'output.

Grazie per questo post interessante. Potresti fornire l'algoritmo corrispondente al primo video che illustra l'articolo? Saluti

Cosa certa! Stasera lavorerò alla decodifica di PatternConfigData. Ci vorrà un po' di tempo, perché quello era un pattern ‘Evolved’, per il quale non ho un metodo di conversione facile alle notazioni nel post del blog.

Aggiornamento: ho aggiunto un'implementazione dello shadertoy sotto il video

Come si sceglie lo stato iniziale?

È uno stato casuale, seminato da una funzione che ho scritto qualche tempo fa che crea un rumore ‘grumoso’. È lo stesso usato negli esempi di shadertoy.


Automi cellulari

Gli automi cellulari sono una classe di sistemi matematici spazialmente e temporalmente discreti caratterizzati da interazione locale ed evoluzione dinamica sincrona. Introdotti dal matematico John von Neumann negli anni '50 come semplici modelli di autoriproduzione biologica, sono modelli prototipici per sistemi e processi complessi costituiti da un gran numero di componenti semplici, omogenei e interagenti localmente. Gli automi cellulari sono stati oggetto di grande attenzione nel corso degli anni a causa della loro capacità di generare un ricco spettro di modelli di comportamento molto complessi a partire da insiemi di regole sottostanti relativamente semplici. Inoltre, sembrano catturare molte caratteristiche essenziali del complesso comportamento cooperativo auto-organizzato osservato nei sistemi reali.

Questo libro fornisce un riassunto delle proprietà di base degli automi cellulari ed esplora in profondità molte importanti aree di ricerca relative agli automi cellulari, tra cui la vita artificiale, il caos, l'emergenza, i frattali, le dinamiche non lineari e l'auto-organizzazione. Presenta anche un'ampia rassegna della proposizione speculativa secondo cui gli automi cellulari potrebbero eventualmente rivelarsi precursori teorici di una fisica discreta basata sull'informazione fondamentalmente nuova. Progettato per essere accessibile a livello universitario junior/senior e oltre, il libro sarà di interesse per tutti gli studenti, ricercatori e professionisti che desiderano conoscere l'ordine, il caos e l'emergere della complessità. Contiene un'ampia bibliografia e fornisce un elenco di risorse di automi cellulari disponibili sul World Wide Web.