Einfache Angabe offener Probleme in der Berechenbarkeitstheorie

14

Ich war auf der Suche nach interessanten und leicht zu formulierenden offenen Problemen in Bezug auf die Berechenbarkeit (verständlich für Studenten, die ihren ersten Kurs in Berechenbarkeit belegen), um Beispiele für offene Probleme zu nennen (und natürlich möchte ich, dass die Studenten das Problem verstehen können, ohne zu viel Neues zu benötigen Definitionen und auch für sie interessant sein).

Ich habe diese Liste gefunden, aber die darin enthaltenen Probleme scheinen für Studenten zu kompliziert zu sein, und es wird einige Zeit in Anspruch nehmen, Definitionen zu geben, bevor das Problem benannt wird. Das einzige Problem, das ich bisher gefunden habe, ist

Ist das diophantinische Problem über rationale Zahlen entscheidbar?

Kennen Sie ein anderes interessantes und leicht zu formulierendes offenes Problem in der Berechenbarkeitstheorie?

computability Kaveh
quelle
1
Welche Vorkenntnisse können wir zB in Bezug auf Automaten, formale Sprachen, Algorithmen voraussetzen?
Raphael
@Raphael, Sie können davon ausgehen, dass Sie Grundkenntnisse in der Berechnungstheorie besitzen, z.
Kaveh
Die Berechenbarkeitstheorie ist abstrakter als beispielsweise die Komplexitätstheorie für Studenten. Ich habe noch nie von ganzen Grundschulklassen für Berechenbarkeitstheorie gehört. was deckst du ab Haben Sie einen Lehrplan online oder ist er einem anderen Online-Lehrplan ähnlich? Es könnte hilfreich sein, die Geschichte von Hilberts 10. Problem zu durchgehen, das den größten Teil des 20. Jahrhunderts offen blieb und eines der "großen" Themen auf dem Gebiet ist. Einige sagen mit Recht, es sei eines der wichtigsten des 20. Jahrhunderts.
vzn

Antworten:

4

(D,≤T)f:D→Dein≤Tbf(ein)≤Tf(b)

Carl Mummert
quelle
1
Wie ist dieses Problem für den durchschnittlichen Studenten interessant ? Gibt es eine bekannte Konsequenz, die aus der Existenz eines solchen Automorphismus abgeleitet werden kann? Ich denke, dass Motivation bei der Einführung neuer Konzepte von größter Bedeutung ist, insbesondere wenn es nur darum geht, den Studenten ein "berühmtes offenes Problem" zu zeigen.
Janoma
2
@Janoma: Die Motivation ist, die globale Struktur der Turing-Abschlüsse zu studieren (und zu verstehen). Es wäre einfach, ohne Beweis einige Ergebnisse wie die Dichte anzugeben und dies als leicht zu bezeichnendes, aber schwer zu lösendes offenes Problem zu bezeichnen.
Carl Mummert