Buone risorse per conoscere modelli di calcolo?

Question

Per curiosità, sto cercando di individuare quale modello di computazione di un sistema con cui lavoro è funzionalmente equivalente a, e dimostrare l'equivalenza. Quanto più a lungo che passo su questo problema e più ho il sospetto che il sistema non è Turing-equivalente. La mia comprensione di macchine di Turing e linguaggi ricorsivamente enumerabili è buona, ma non so molto di automi con funzionalità inferiori (per esempio automi a pila), quindi non sono sicuro di come procedere.

In primo luogo, qualcuno può consigliare una buona risorsa per conoscere diversi modelli di calcolo? Mi interessa grammatiche, lingue e automi, e come per dimostrare l'equivalenza e la differenza tra tutti loro. Idealmente la risorsa sarebbe abbattere tutti gli elementi di ogni modello in grande dettaglio e confrontarli.

In secondo luogo, c'è un approccio generale o di un quadro che deve essere utilizzato quando si cerca di montare un sistema su uno di questi modelli di calcolo?

Answer 1

mi consiglia un buon libro di testo su informatica (Nel mio Uni Naturalmente, sto studiando da Introduzione di Sipser alla teoria della computazione , che è molto buono a mio parere. si potrebbe anche trovare un libero da manuale che insegna la stessa cosa, ma non ho alcuna esperienza con uno così non posso consigliare).

L'altro approccio sarebbe probabilmente solo di leggere su Wikipedia. Si può effettivamente ottenere un sacco di chilometraggio fuori degli articoli di Wikipedia, se si sa cosa si sta cercando e in quale ordine. Inoltre, se qualcosa non è chiaro, di solito si può google e trovare ulteriori risorse su quel particolare argomento.

Naturalmente, questo sarà non essere buono come un vero e proprio libro di testo, ma è un buon posto per iniziare in questo momento , ed è gratuito.

Come punto di partenza, io consiglierei di leggere sui seguenti argomenti (nell'ordine elencato):

1. deterministico Finite Automaton
2. non deterministico Finite automa , e la loro equivalenza DFA.
3. linguaggi regolari e loro equivalenza a DFA.
4. automi a pila
5. senza contesto Grammatiche , e la loro equivalenza automi a pila.
6. Chomsky Gerarchia
7. macchine di Turing

Questo dovrebbe fornire una breve introduzione alla maggior parte dei modelli computazionali la gente parla.    2 : mi consiglia un buon libro di testo su informatica (Nel mio corso Uni, I' m studiando da Introduzione Sipser alla teoria della computazione , che è molto buono in la mia opinione). L'altro approccio sarebbe probabilmente solo di leggere su Wikipedia. Si può effettivamente ottenere un sacco di chilometraggio fuori degli articoli di Wikipedia, se si sa cosa si sta cercando e in quale ordine. Inoltre, se qualcosa non è chiaro, di solito si può google e trovare ulteriori risorse su quel particolare argomento. Come punto di partenza, io consiglierei di leggere sui seguenti argomenti (nell'ordine elencato): 1. 1 : http://www.amazon.com/Introduction -Teoria-calcolo-Second-Michael / dp / 0534950973 / ref = sr_1_1? ie = UTF8 & s = libri & qid = 1.263.282,346 mila & sr = 8-1

Answer 2

Le lezioni video dal seguente link dà buona introduzione alla teoria della computazione. Questa è una delle migliori risorse su questo argomento.

Video Lezioni sulla teoria della computazione dal Prof. Shai Simonson

Answer 3

Un testo più vecchio che può essere difficile da trovare è Hopcroft e di Ullman "Introduzione alla teoria degli automi, Lingue, and Computation". Ci sono un certo numero di edizioni --- Ho sentito dire che il '79 è il migliore, in quanto tira i pugni minor numero di introduzione di cose complesse. E 'una legittima, anche se piccolo libro di testo, e introduce tutto il campo, non solo quello che stai cercando. Suggerisco questo sul probabile vana speranza che forse una di quelle prove "più complicato" altre fonti di lasciare fuori può essere la vostra chiave.

Come punto di partenza più dolce, ci sono alcuni a portata di mano "a benchmark" lingue.

• Se il modello possono di riconoscere il linguaggio di tutte le stringhe in cui ci sono lo stesso numero di As e B in una stringa, allora è almeno più potente di FSM.
• Se non può, allora possono essere equivalente al FSM.
• Allo stesso modo, se il vostro modello di possono riconoscere il linguaggio di tutte le stringhe in cui lo sono lo stesso numero di As, Bs e Cs in una stringa, allora è più potente di una CFG, o PDA.

Queste "lingue di riferimento" sono in realtà solo le funzioni sotto mentite spoglie --- il primo chiede in sostanza se 2 numeri unari sono uguali, il secondo chiede se 3 numeri unari sono uguali. Essi sono belle e semplici, e sono ben noti per essere al di sopra o al di sotto delle capacità dei modelli particolari. Non so più semplici per le macchine più complesse, così si può essere da soli.

Si noti che per il modello "LBA", automi linearmente limitata, credo che non ci sia il linguaggio naturale noto che è calcolabile con una TM, ma non un LBA. Questa affermazione è tratto dai ricordi sfumati, in modo da non prendere come una dimostrazione formale. :)

Nota (ultimo) che le lingue "a benchmark" NON SONO stabilire l'uguaglianza. Vale a dire, se il modello non si può paragonare 2 numeri unari, che fa non significa che sia necessariamente equivalente a un FSM, potrebbe essere ancora più debole. Le lingue stabilirebbe solo ciò che è più grande di potere, o inferiore al potere.

In modo del tutto (completamente) traccia diversa, il libro di Sipser fa fare prove di equivalenza tra le espressioni regolari e FSM, nonché tra PDA e CFGS. Io non sono sicuro di come utile che sarà, come si è abbastanza vago su quale tipo di modello di calcolo si sta valutando, ma se sei morto-impostato sull'equivalenza, questi possono essere buoni punti di partenza.