computability

3Hitze

2Antwort

Gibt es rekursiv aufzählbare Probleme, die nicht RE-hart sind?

Die Berechenbarkeit Klasse, die ich nehme, erklärt mehrere Sprachen, die in RE sind - REC (rekursiv aufzählbar aber nicht rekursiv, das heißt auflösbar durch eine Turing-Maschine Nicht-Halten). Es zei

1Hitze

1Antwort

Berechenbarkeit: SAT-Formel mit beschränkter Anzahl von Klauseln

Definieren Sie SAT2016 = {\ phi | \ phi ist eine CNF-Formel mit höchstens 2016 Klauseln}. Annahme von P \ neq NP, ist SAT2016 NP-vollständig? Da die Anzahl der Literale in jeder Klausel nicht begrenzt

5Hitze

8Antwort

Löst das Anhalten Problem einfacher als Leute denken?

Obwohl der allgemeine Fall unentscheidbar ist, lösen viele Menschen immer noch Probleme, die für den täglichen Gebrauch gut genug sind. In Cohen's Doktorarbeit über Computerviren zeigte er, wie Virens

0Hitze

1Antwort

Berechenbarkeit eines Wahrscheinlichkeitstheorie-Problems

Dies ist ein Problem, das ich für einen Kurs gelöst habe und ich habe mich gefragt, ob meine Lösung korrekt ist. Normalerweise würde ich ein reines Mathematikproblem nicht posten, außer dass ich glaub

8Hitze

1Antwort

Was sind alle bekannten Sprachen, die Turing-Maschinen nicht akzeptieren können?

Für example kann die Sprache von Turing-Maschinen, die ihre eigene Codierung nicht akzeptieren, von keiner Turing-Maschine akzeptiert werden.

6Hitze

1Antwort

Ist PI eine errechnete Zahl?

AFAIK, turing berechenbare Zahlen sind Zahlen, deren i-ter Index von einer Turing-Maschine zurückgegeben werden kann. Also wäre eine nicht-berechenbare Zahl etwas wie eine Zahl, deren Dezimalpunkte en

16Hitze

4Antwort

Gibt es eine Black-Box-Methode, um festzustellen, ob ein Sortieralgorithmus stabil ist?

In JavaScript (etwas anderswo anwendbar), wo Sie nicht wissen, welche Zielimplementierung Ihr Code läuft, gibt es eine Möglichkeit zu erkennen, ob der zugrundeliegende Sortieralgorithmus (von Array.so

6Hitze

4Antwort

Eine unendliche Sprache kann nicht regelmäßig sein? Was ist eine endliche Sprache?

Ich lese in einem Buch auf Berechenbarkeit: (Kleenes Satz) ist eine Sprache, regelmäßig, wenn und nur wenn es aus endlichen Sprachen erhalten werden kann, indem die drei Operationen Vereinigung Anwend