Gibt es ein einfaches Beispiel für Mengen wie aber nicht ?

7

Ich frage mich , ob es ein einfaches Beispiel von Sätzen ist und , so dass ist Turing-reductible zu , aber nicht viele-zu-eins reductible zu . $A$ $B$ $A$ $B$ $B$

turing-machines reductions Pintoch
quelle

wenn

A \leq_{1} B \to A \leq_{m} B \to A \leq_{T} B

$A \leq_1 B \rightarrow A \leq_m B \rightarrow A \leq_T B$ aber die umgekehrte Reihenfolge ist nicht wahr. Deshalb lautet die Antwort ja

M ama D

11

Zum Beispiel setzt $H = \{x \, |$ Turingmaschine mit Index $x$ hält bei Eingabe $x\}$ und $\overline{H} = \{x \, |$ Turing-Maschine mit Index $x$ stoppt nicht bei Eingabe $x\}$ .

Denn wenn , dann wäre rekursiv aufzählbar und daher wäre rekursiv, was ein Widerspruch ist. $\overline{H} \leq_m H$ $\overline{H}$ $H$

Auf der anderen Seite , weil es eine Turing-Maschine gibt, bei der Orakel erkennt . Diese Maschine für die Eingabe prüft nur und negiert die Antwort. $\overline{H} \leq_T H$ $H$ $\overline{H}$ $x$ $x \in H$

Martin Jonáš
quelle

Mit meinen Sie die Menge aller TMs, die anhalten, oder ähnliches?

H

$H$

Luke Mathieson

Ja, mit meine ich eine Reihe aller TMs, die anhalten. Ich werde es in die Antwort aufnehmen.

H

$H$

Martin Jonáš

0

Der Hauptunterschied (oder mindestens ein wichtiger Unterschied) besteht darin, dass Turing-Reduzierungen auf Orakel basieren, wohingegen Mehrfachreduzierungen eine insgesamt berechenbare Funktion erfordern (dh Sie müssen in der Lage sein, alle Eingaben auf etwas abzubilden). In diesem Sinne können wir ein ziemlich klares Beispiel erhalten:

Betrachten Sie die Gruppe von Turing-Maschinen, die bei einer festen Eingabe anhalten (aus Gründen der Argumentation ist eine leere Eingabe gut genug), und die Gruppe, die nicht bei derselben festen Eingabe anhält. Es sollte klar sein, dass dies Turing-Äquivalent ist (wenn wir ein Orakel für eines haben, können wir es verwenden, um das andere zu beantworten - führen Sie einfach das Orakel auf der Eingabe aus und geben Sie die entgegengesetzte Antwort).

Wenn wir andererseits eine berechenbare Funktion hätten, die Maschinen, die nicht anhalten, in solche konvertiert, die dies tun, und umgekehrt, könnten wir das Problem des Anhaltens entscheiden.

Luke Mathieson
quelle

1

Der letzte Satz verblüfft mich.

Andrej Bauer

2

Es ist wahr, dass die Stoppmenge und ihr Komplement Turing-Äquivalent sind. Aber der Grund dafür, dass sie nicht viele reduzierbar sind, ist falsch. Es ist durchaus möglich, zwischen nicht berechenbaren Mengen eine Eins-zu-Eins-Reduktion zu erzielen (nehmen Sie eine beliebige nicht berechenbare Menge und die Menge ). Sie sollten stattdessen Martins Antwort akzeptieren.

H

$H$

N ∖ H

$\mathbb{N} \setminus H$

S

$S$

{n + 1 ∣ n \in S}

$\lbrace n + 1 \mid n \in S\rbrace$

Andrej Bauer

@AndrejBauer, ganz richtig, unglaublich schlampig von mir. Ich werde es für die Nachwelt reparieren, aber ich stimme zu, dass Martins Antwort sowieso überlegen ist.

Luke Mathieson

0

Sei eine beliebige nichttriviale Sprache wie und sei die leere Sprache . $A$ $\{a\}$ $B$ $\emptyset$

$A$ ist Turing-reduzierbar auf da wir bei einem Orakel für die leere Sprache bestimmen können, ob eine Eingabezeichenfolge oder nicht. (Wir brauchen nicht einmal das Orakel zu benutzen.) $B$ $a$

Aber ist nicht auf reduziert, da es nichts gibt, dem die Eingabe . $A$ $B$ $a$

usul
quelle

Gibt es ein einfaches Beispiel für Mengen wie aber nicht ?

Antworten: