Conteggio con le TM spazio costante delimitate

Question

Il problema, proveniente da una questione intervista, è:

Hai un flusso di numeri in arrivo nella gamma 0-60.000 e si deve una funzione che avrà un numero da tale intervallo e restituisce la contare di insorgenza di tale numero fino a quel momento. Dare un adeguato Struttura dei dati / algoritmo per implementare questo sistema.

Il flusso è infinito, quindi se le strutture di dati di dimensione fissa ri utilizzati, cioè tipi primitivi in ??Java o C, essi traboccano. Quindi non v'è la necessità di strutture di dati di uso che hanno una dimensione che cresce nel tempo. Come sottolineato dall'intervistatore, la memoria occupata da quelle strutture dati saranno divergere.

Il modello di calcolo è una macchina di Turing con tre nastri:

• infinito sola lettura unidirezionale nastro ingresso;
• spazio delimitato costante lettura-scrittura nastro lavoro a due vie;
• infinito sola scrittura nastro uscita unidirezionale.

Il motivo principale per scegliere il modello di cui sopra è che nel mondo reale non c'è praticamente alcun limite alla quantità di input che possono essere acquisite utilizzando una tastiera o di una connessione di rete. Inoltre, non v'è praticamente alcun limite alla quantità di informazioni che possono essere visualizzate su amonitor nel corso del tempo. Ma la memoria è limitata e costosa.

I modellato il problema come il problema di riconoscere la lingua L di tutte le coppie (numero, numero di occorrenze finora).

Come corollario del Teorema 3.13 in Hopcroft-Ullman So che ogni lingua riconosciuta da una macchina spazio delimitato costante è regolare.

Ma, in ogni momento, il linguaggio L è un linguaggio finita, perché il numero di coppie di essere riconosciuti è finita: 60001. Quindi non posso usare il lemma di pompaggio per linguaggi regolari per dimostrare che tale lingua non è regolare.

C'è un modo per completare la mia prova?

La domanda iniziale è qui .

Answer 1

Vi faccio una spiegazione che non differisce nel contenuto della risposta accettata, ma porta sul retro domanda al regno di linguaggi regolari.

La lingua si sta trattando può essere definito come segue. Let $ s \ in \ Sigma ^ {\ mathbb {N}} $ essere un (numerabile) sequenza infinita di simboli da alcune finita alfabeto $ \ Sigma $, e lasciare $ s [1: i] $ essere il prefisso del primo $ I $ simboli in $ s $. Nel tuo caso $ s $ è l'ingresso e e $ \ Sigma $ è interi positivi non negativi $ \ {0, \ ldots, 60000 \} $. $ L (s) $ può essere definito come un linguaggio di triple $ (s [1: i], una, j) $ dove $ (s [1: i], una, j) \ a L (s) $ se e solo se ci sono $ j $ occorrenze di $ a $ a $ s [1: i] $. Si convinca, utilizzando il lemma di pompaggio, che per ogni $ fisso s $, $ L (s) $ non è regolare. Poi convincere te stesso che se una memoria limitata Macchina di Turing poteva risolvere il problema, potrebbe anche riconoscere la non regolare lingua $ L (s) $. Questo argomento dovrebbe funzionare anche se fissiamo $ a $ e definire un simile linguaggio di $ L (s, a) $.

Questi tipi di esempi sono la ragione per cui il nostro modello computazionale di scelta (i nostri = la comunità algoritmi) è la macchina di parola RAM, e si presuppone che dimensione della parola cresce con la dimensione di ingresso. Questo dovrebbe modellare il fatto che i casi ci troviamo di fronte, in realtà crescere, così fa la memoria dei nostri computer. Naturalmente, ad un certo punto affronteremo limiti fisici dell'hardware: c'è solo la memoria così tanto che si può accedere velocemente da un singolo / un numero finito di processori. Un modo per andare oltre questi limiti è gerarchie di memoria e la modellazione diventa più complicata, ma c'è qualche molto bella teoria così (vedi modelli di memoria esterni e algoritmi della cache-ignaro).

Answer 2

Per semplicità assumere, non si dispone di 600.000 numeri, ma solo 1. Ad un certo tempo $ I $ un certo numero di 1s sono stati inviati. Noi chiamiamo questo numero prefix del torrente. Ci sono infiniti possibili prefissi.

Poiché c'è solo un nastro opera di perimetro, il TM può avere al più un numero costante di configurazioni. Così, ci sono almeno due differenti prefissi, che sarebbe piombo per la stessa configurazione. In entrambi i casi il TM deve uscita lo stesso numero, per qualsiasi richiesta seguente. Quindi il TM non può calcolare la funzione desiderata.

Spero che questo è convincente, anche se non è super-formale.