Wie viele Turingmaschinen gibt es, die in der Zeit oder im Raum an Eingängen der Länge laufen ?

Ich denke, der halbe Kampf bei der Beantwortung dieser Frage liegt darin, sie genau zu formulieren! Eine Suchmaschine taucht nicht viel auf, deshalb habe ich mich gefragt, ob dies eine bekannte oder gut untersuchte Frage ist.

Meine Gedanken: Ich denke, der einfachste Weg, diese Frage zu formulieren, ist wie in meinem Titel: Angesichts der Konstanten , wie viele TMs gibt es, die in Schritten oder weniger auf allen Eingaben von ausgeführt werden Größe , und wie viele TMs verwenden Bandquadrate oder weniger an allen Eingängen der Größe ? Dies scheint die direkteste und einfachste Möglichkeit zu sein, die Frage zu stellen, aber wir möchten sie möglicherweise anders formulieren - zum Beispiel, wenn eine Funktion , wie viele TMs in der Zeit auf Eingaben der Größe für alle (oder wie "dicht" sind diese TMs)? Das scheint mir schwieriger zu sein. $t,s,k \in \mathbb{N}$ $t$ $k$ $s$ $k$ $p(k)$ $p(k)$ $k$ $k$

Wir sollten wahrscheinlich ein Bandalphabet (oder eine Godel-Nummerierung ??) reparieren. Wir könnten zwei TMs mit unterschiedlichen, aber isomorphen Zustandsdiagrammen als gleich oder unterschiedlich betrachten.

Das unmittelbare Problem ist, dass es unendlich viele gibt: Nehmen Sie ein TM, das die Kriterien erfüllt, und fügen Sie "tote Zustände" hinzu. Ich kann mir zwei Möglichkeiten vorstellen, damit umzugehen. Das erste (was mir nicht gefällt) ist das Hinzufügen eines zusätzlichen Parameters: Wie viele TMs, deren Beschreibung die Länge erfüllen die Kriterien? Die zweite (die ich bevorzuge) besteht darin, zwei TMs zu berücksichtigen , die für Eingaben der Größe äquivalent sind, wenn die TMs für alle diese Eingaben genau das gleiche Verhalten haben (geben Sie die gleichen Zustände ein und schreiben / bewegen Sie sich identisch auf dem Band). Dann würden wir uns auf das minimale TM in jeder Äquivalenzklasse beschränken oder einfach fragen, wie viele Äquivalenzklassen die Kriterien erfüllen. $\leq L$ $\leq k$

Bearbeiten: Wie Vor in den Kommentaren hervorhob, besteht das Problem beim zweiten Ansatz darin, dass es zu diesem Zeitpunkt im Grunde dasselbe ist wie eine Schaltung. Wie wäre es mit dem ersten? Oder gibt es eine schönere Möglichkeit, diese Frage zu formalisieren?

Alle Referenzen / Literatur, Gedanken oder Antworten wären sehr interessant und geschätzt!

complexity-theory reference-request turing-machines combinatorics usul
quelle

Wenn Sie auswählen , haben Sie verschiedene boolesche Funktionen . Wenn also k <= t ist, erhalten Sie mindestens verschiedene TMs ... und vielleicht reichen sie aus, um andere Variationen / Parametrisierungen nicht mehr zu zählen :-).

Σ = {0, 1}

$\Sigma = \{0,1\}$

2^{(2^{k})}

$2^{(2^k)}$

{0, 1}^{k} \to {0, 1}

$\{0,1\}^k \rightarrow \{0,1\}$

2^{(2^{k})}

$2^{(2^k)}$

Vor dem

@Vor, ich verstehe, warum es so viele boolesche Funktionen gibt, aber warum laufen sie alle in der Zeit ... hmm, ich denke, weil wir einfach für jede einen anderen DFA erstellen und ihn zum Zustandsdiagramm unserer machen TM? OK, um die Frage interessant zu machen, sollte ich darüber nachdenken, neue Einschränkungen neu zu definieren oder hinzuzufügen.

O (k)

$O(k)$

Usul

Es könnte einfacher sein, nach Sprachen anstatt nach TMs zu fragen, und in diesem Fall bezieht sich diese Frage tatsächlich auf offene Fragen der Trennung von Komplexitätsklassen. Mit anderen Worten, es gibt wahrscheinlich Möglichkeiten, dies zu formulieren, die der Frage nach P =? NP usw. entsprechen. Eine andere interessante Idee könnte sein, die Geschwindigkeit von TMs zu berücksichtigen, dh das Verhältnis von ... auch dieses Thema kann empirisch etwas für "kleine" Sprachen untersucht werden ...

t (n) / s (n)

$t(n)/s(n)$

vzn

Antworten:

Betrachten Sie bei gegebenem die Menge von wobei definiert ist $k$ $\mathcal{M}_k = \{ M_i \mid i \in \mathbb{N} \}$ $M_i$

if |x| = k
  accept
else
  simulate TM i on x

Die Menge ist eine Teilmenge der Turing-Maschinen, die Sie für alle zählen möchten . Da es unendlich ist, ist auch die Menge, die Sie zählen möchten, unendlich. $\mathcal{M}_k$ $s,t$

Soweit ich das beurteilen kann, ist dieses Ergebnis gegen alle von Ihnen auferlegten Einschränkungen stabil, solange Sie nicht festlegen, dass alle möglichen Turing-Maschinen endlich sind.

Raphael
quelle

Was ist mit dem Hinzufügen der folgenden Äquivalenz: Zwei Maschinen sind äquivalent "mod k", wenn sie sich bei Eingaben der Größe k gleich verhalten (möglicherweise Modulo-Bisimulation). Nun ist es sinnvoll, nach der Größe der Äquivalenzklassen mod k zu fragen.

Cody

@cody Diese Klassen sind auch alle unendlich. Ändern Sie in meiner Konstruktion den elseZweig auf count to i on the tape; rejectund Sie erhalten eine unendliche Menge von Akzeptoren für ; Die gleiche Konstruktion funktioniert grundsätzlich für alle (entscheidbaren) Sprachen.

Σ^{k}

$\Sigma^k$

Raphael

Es tut mir leid, ich bin verwirrt, es scheint mir, dass alles in Ihrem 'else'-Zweig irrelevant ist "mod k", da es das Verhalten in dem Fall angibt, in dem | x | ist -not- k.

Cody

@cody: Ja und nein. Alle beschriebenen Maschinen nehmen die gleiche Teilmenge von , so sie sind äquivalent modulo (wenn ich das richtig , was Sie wollten verstehen). Es gibt jedoch unendlich viele solcher Zweige, so dass die Äquivalenzklasse unendlich viele Elemente enthält. Und soweit ich behaupte, gilt dies für alle Äquivalenzklassen, da eine ähnliche Konstruktion immer funktioniert. (Im Wesentlichen lautet die Aussage: Jede Sprache wird von unendlich vielen TMs akzeptiert. Oder sogar: Für jedes TM gibt es unendlich viele andere, die der Ausgabe entsprechen.)

Σ^{k}

$\Sigma^k$

k

$k$ else

Raphael

Mein Vorschlag ist daher, alle TMs zu identifizieren, die sich außerhalb von unterschiedlich verhalten . In diesem Fall ist immer noch klar, dass es unendlich viele Klassen von Maschinen gibt, die dieselbe Sprache in akzeptieren . Es ist jedoch nicht klar, dass es unendlich viele von denen gibt, die in begrenztem Raum und Zeit arbeiten.

Σ^{k}

$\Sigma^k$

Σ^{k}

$\Sigma^k$

Cody

Ihre Frage hängt eng mit dem Problem des beschäftigten Bibers zusammen . Es fragt nach der maximalen Anzahl von Symbolen einer State-Turing-Maschine mit 2 Ausgabesymbolen, die Schreibvorgänge immer anhalten, bevor sie angehalten werden. Die so definierte Funktion von ist nicht berechenbar. $n$ $n$

vonbrand
quelle

Sicher, es gibt einen Zusammenhang, aber ich interessiere mich hauptsächlich für die Frage nach einer berechenbaren Funktion ... Ich sehe in diesem Fall nicht, wie man BB verwendet.

t (k)

$t(k)$

Usul

Sie stellen einige Fragen und formulieren einige interessante Ideen, die sich im Allgemeinen fast auf offene Fragen zur Trennung von Komplexitätsklassen beziehen. Zum Beispiel kann P =? NP so umformuliert werden, dass gefragt wird, wie viele NP (-hard) Sprachen in P-Zeit ausgeführt werden können. Es gibt jedoch wahrscheinlich nicht zu viele theoretische (oder andere) Ergebnisse in diesem Bereich. Es gibt einige theoretische Arbeiten, die die zeitliche und räumliche Komplexität von SAT einschränken und Ihre Frage berühren. Die vielleicht am nächsten liegende Forschung ist jedoch die empirische Analyse von TMs, die in der anderen Antwort von vonbrand angedeutet wird, z. B. mit vielbeschäftigter Biberforschung.

Es gibt ähnliche, aber relativ seltene Untersuchungen, die sich mit empirisch erzeugten TMs mit "Uhren", z. B. P-Zeit usw., befassen. Hier ist eine solche Referenz aus dem Jahr 2013. Sie zählt TMs mit P-Zeit-Uhren auf und untersucht / für fraktale Muster in den resultierenden / erzeugte "Zeit-Raum-Diagramme" (auch "Computertableaus" genannt). Ein anderer Ansatz besteht darin, "kleine endliche" Stichproben zu betrachten, z. B. die Begrenzung von (und auch anderer Parameter wie aufgezählte TM-Zustände). $t, s, k$

Fraktale Dimension vs. Rechenkomplexität Joost J. Joosten, Fernando Soler-Toscano, Hector Zenil

vzn
quelle