Zählen Sie mit konstantem Raum begrenzter TMS

Question

Das Problem, das aus einer Interviewfrage stammt, ist:

Sie haben einen Strom eingehender Zahlen in Bereich von 0 bis 60000 und eine Funktion, die eine Zahl aus diesem Bereich entnimmt und die Anzahl der Auftreten dieser Zahl bis zu diesem Moment zurückgibt. Geben Sie eine geeignete Datenstruktur/einen geeigneten Algorithmus zur Implementierung dieses Systems an.

Der Stream ist unendlich. Wenn die Datenstrukturen fester Größen verwendet werden, werden dh primitive Typen in Java oder C überlaufen. Es ist also erforderlich, Datenstrukturen zu verwenden, die eine Größe haben, die im Laufe der Zeit wächst. Wie der Interviewer hervorgeht, wird der von diesen Datenstrukturen besetzte Speicher abweichen.

Das Berechnungsmodell ist eine Turing -Maschine mit drei Bändern:

• unendlich schreibgeschütztes Einweg-Eingangsband;
• konstantes lachgebundener Leseschreiber zwei Wege Arbeitsband;
• Unendlichem Schreibbetriebsband.

Der Hauptgrund für die Auswahl des obigen Modells ist, dass in der realen Welt praktisch keine Grenze für die Eingabemenge besteht, die mithilfe einer Tastatur oder einer Netzwerkverbindung erfasst werden kann. Außerdem gibt es praktisch keine Begrenzung für die Informationsmenge, die im Laufe der Zeit auf Amonitor angezeigt werden kann. Aber das Gedächtnis ist begrenzt und teuer.

Ich habe das Problem als das Problem modelliert, um die Sprache L aller Paare zu erkennen (Anzahl, Anzahl der bisherigen Vorkommen).

Als Folge des Satzes 3.13 in Hopcroft-Ullman weiß ich, dass jede von einer konstant gewordene Maschine erkannte Sprache regelmäßig ist.

In jedem Moment ist die Sprache L jedoch eine endliche Sprache, da die Anzahl der zu erkennenden Paare endlich ist: 60001. Ich kann also nicht das Pumping -Lemma für reguläre Sprachen verwenden, um zu beweisen, dass eine solche Sprache nicht regelmäßig ist.

Gibt es eine Möglichkeit, meinen Beweis zu vervollständigen?

Die ursprüngliche Frage ist hier.

Answer 1

Lassen Sie mich eine Erklärung geben, die sich in den Inhalten von der akzeptierten Antwort nicht unterscheidet, sondern die Frage in den Bereich der regulären Sprachen zurückbringt.

Die Sprache, mit der Sie es zu tun haben, kann wie folgt definiert werden. Sei $ s in sigma^{ mathbb {n}} $ a (zählbar) unendlich symbole aus einem endlichen Alphabet $ sigma $ und sei $ s [1: i] $ das Präfix des ersten $ i $ symbole in $ s $. In Ihrem Fall ist $ s $ der Input und $ sigma $ ist die nichtnegativen positiven Ganzzahlen $ {0, ldots, 60000 } $. $ L (s) $ kann als eine Sprache von Dreifachstücken $ (s [1: i], a, j) $ definiert werden, wobei $ (s [1: i], a, j) in l (s) $ wenn und nur wenn es $ j $ Ereignisse von $ a $ in $ s [1: i] $ gibt. Überzeugen Sie sich selbst mit dem Pumping Lemma, dass für alle festgelegten $ s $ l (s) $ nicht regelmäßig ist. Überzeugen Sie sich dann, dass ein begrenzter Gedächtnis-Turing-Maschine Ihr Problem lösen könnte, sie auch die nicht reguläre Sprache $ l (s) $ erkennen könnte. Dieses Argument sollte funktionieren, auch wenn wir $ a $ reparieren und eine ähnliche Sprache $ l (s, a) $ definieren.

Diese Art von Beispielen ist der Grund, warum unser Rechenmodell der Wahl (unsere = die Algorithmen -Community) die Wort -RAM -Maschine ist, und wir gehen davon aus, dass die Wortgröße mit Eingangsgröße wächst. Dies soll die Tatsache modellieren, dass die Erinnerung an unsere Computer auch als die Fälle, mit denen wir in der Realität konfrontiert sind, wachsen. Natürlich werden wir irgendwann physische Grenzen der Hardware ausgesetzt sein: Es gibt nur so viel Speicher, auf das schnell von vielen Prozessoren zugegriffen werden kann. Eine Möglichkeit, über diese Grenzen hinauszugehen, sind Gedächtnishierarchien und die Modellierung wird komplizierter, aber es gibt auch eine sehr schöne Theorie (siehe externe Speichermodelle und cache-obliven Algorithmen).

Answer 2

Der Einfachheit halber haben Sie keine 600.000 Zahlen, sondern nur 1. Zu einem bestimmten Zeitpunkt $ i $ eine bestimmte Anzahl von 1S wurden gesendet. Wir nennen diese Nummer die Präfix des Stroms. Es gibt unendlich viele mögliche Präfixe.

Da es nur ein Arbeitsband mit konstanter Größe gibt, kann das TM höchstens eine konstante Anzahl von Konfigurationen haben. Somit gibt es mindestens zwei verschiedene Präfixe, das würde führen zur gleichen Konfiguration. In beiden Fällen muss der TM für jede folgende Anfrage dieselbe Zahl ausgeben. Daher kann der TM die gewünschte Funktion nicht berechnen.

Ich hoffe, das ist überzeugend, obwohl es nicht superformal ist.