Dabei kann davon ausgegangen werden, dass das wort aus mindestens einem Zeichen besteht(also keine leere Eingabe)

Hallo,

ich möchte eine Turing-Maschine aufstellen, deren Algorithmus nach eintreten der ersten 1 die restlichen Einser um eine Einheit nach rechts verschiebt und den Abststand zu weiteren Einsern um eine 0 verringert.

Aus 00011110000100

wird 00001111000100

Den Ansatz füge ich hinzu. Was muss ich beachten?

Hallo,

ich solle eine Turing-Maschine angeben, die eine 1 nach rechts verschiebt, wobei der Abstand zu einer weiteren 1 um eine 0 verringert wird.

Wie kann man dies angeben?

Muss ich ganz links/rechts starten?

LG

In der Realität will man doch eh immer nur Kryptocoins von A nach B senden. Was bringt es also, dass z.B. Ethereum turingvollständig ist?

Hallo! Ich bräuchte Hilfe bei dieser Aufgabe:

"Sei L = {<M> | M akzeptiert, wenn die Eingabelänge durch 5 teilbar ist}. Zeigen Sie durch Reduktion, dass L unentscheidbar ist."

Ich weiß, dass man jetzt einen Widerspruchsbeweis aufstellen sollte, indem man eine bekanntlich unentscheidbare Sprache U auf L reduziert. Dazu nimmt man an, dass L entscheidbar wäre und dafür somit ein Entscheider existiert. Daraus baut man dann eine Entscheider-TM T für diese unentscheidbare Sprache U, was einen Widerspruch erzeugt.

Welche unentscheidbare Sprache sollte man hier bestenfalls benutzen (vielleicht das Wortproblem ATM) und wie würde dann die TM T im Ansatz funktionieren?

Danke!

Sei L eine entscheidbare Sprache. Zeigen Sie dass die Sprache L′ auch entscheidbar ist, wobei

L′ = {w | w · w^r ∈ L},

und w · w^r ist die Konkatenierung des Wortes w mit seiner Umkehrung.

kann mir hierbei jemand helfen?

• Schreibt ein Turing-Programm, das möglichst viele Male "ab" auf das Band schreibt
• Bedingungen:
• Die Turingmaschine muss halten
• Das Eingabealphabet besteht aus {1; 5}
• Das Bandalphabet besteht aus maximal 7 Zeichen
• Zu Beginn ist das Band leer
• Das Programm soll auf dem Turing-Simulator von Mathe-Prisma laufen
• Anforderungen:
• Die Anzahl der Zustände der Maschine sollte so gering wie möglich gehalten werden
• Um eine gute Bewertung zu erhalten, muss die Anzahl der 15en größer als 2^#Zustände sein.

Trotz mehrfacher Recherche verstehe ich nicht wie sie funktioniert. Kann mir einer helfen?

Moin,

ich möchte mich gerne weiterbilden im Bezug zu Informatik, und lese gerade Dinge über die Turingmaschine und deren Konfiguration.

Ich komme jedoch nicht damit zurecht, wie sowas geht:

"Entwickeln Sie eine Turingmaschine, die eine Eingabe, eine beliebige acht Bit lange positive Dualzahl, in eine negative Dualzahl wandelt. Geben Sie die Turingmaschine als 7-Tupel mit Übergangstabelle an. Lassen Sie die Turingmaschine in einer gültigen Anfangskonfiguration starten und in einer gültigen Finalkonfiguration stoppen."

Ich möchte diese Aufgabe sehr gerne lösen, aber komme einfach nicht voran. Über einen möglichen Lösungsweg oder weiterführender Hilfestellung wäre ich sehr dankbar!

Hallo zusammen,

kann mir jemand von euch sagen, wie man eine Turingmaschine erstellt, welche z.B Worte aus dem Alphabet (a, b, c, d) sortiert? Am Ende sollten dann die a‘s vorne stehen und die d‘s als letztes.

Danke für eure Hilfe!

Hallo,

ich soll eine Turingmaschine modellieren, die folgendes macht:

-Modulo 2 einer Unärzahl m, sodas für das Ergebnis gilt:

1. 0, wenn m durch zwei teilbar
2. 1 sonst.

Alpabet sei [0,1].

Meine Idee war folgende:

Ziehe immer zwei ab, solange bis entweder 0 oder 1 dasteht.

m=4
1111
1100
0000 => Rest 0

m=3
111
100 => Rest 1

Nun jetzt mein Problem:

Die TM kann sich keine Werte merken, also wie realisiere ich das er nur dann abzieht wenn wirklich noch zwei 1'en zum abziehen da sind? Er muss irgendwie wissen das er nur zwei Einsen aufeinmal entfernen darf oder er entfernt garnichts.

Oder ist mein Konzept falsch?

Vielen Dank für hilfreiche Antworten.

mfg werdas34

Und was ist das Problem mit NP bzw. warum existieren die verschiedenen Probleme

Hallo zusammen , was ist der Unterschied zwischen dem Eingabealphabet und dem Bandalphabet in Turingmaschine und im folgenden Beispiel,warum das Zeichen X vom Eingabezeichen ausgeschlossen ist , Also ,was bedeutet das überhaupt ? Danke im voraus . Grüße