Problem bei Konzept/Umsetzung der Turingmaschine?

Hallo,

ich soll eine Turingmaschine modellieren, die folgendes macht:

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

0, wenn m durch zwei teilbar
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

3 Antworten

Vom Beitragsersteller als hilfreich ausgezeichnet

triopasi

Nutzer, der sehr aktiv auf gutefrage ist

im Thema programmieren

15.01.2018, 09:30

Meinst du nicht Binärzahl?

Dann überleg dich mal wann eine solche durch 2 teilbar ist.. Zeit für ein bisschen Theorie muss sein ;)

Woher ich das weiß:Studium / Ausbildung – Informatikstudium

gfntom

15.01.2018, 09:56

Wie man aus den Beispielen erkennt, handelt es sich um Unärzahlen - so wie auch in der Fage angeführt, nicht um Binärzahlen.

triopasi

15.01.2018, 10:03

@gfntom

Ach so ist das gemeint.

Dann überlege doch mal wie man erkennt ob eine solche Zahl durch 2 teilbar ist..

gfntom

15.01.2018, 10:09

@triopasi

Mach ich gerne, bin aber nicht der Fragesteller!

triopasi

15.01.2018, 10:22

@gfntom

Ops :D Das war an ihn gerichtet xD

werdas34

Beitragsersteller

15.01.2018, 10:41

@triopasi

Eine Zahl ist durch 2 teilbar wenn der Rest 0 ist. Wenn eine 1 rauskommt ist diese Zahl nicht durch 2 teilbar. Das bringt mich aber auch nicht weiter. Oder meinst du was anderes?

Wäre das Alphabet um eine Einheit erweitert z.B. [0,1,2] könnte ich es lösen. Aber mir bleibt es mit Modulo 2 ein Rätsel, da die TM prüfen muss ob es noch zwei Einsen gibt, die abgezogen werden können. Aber ich nicht weiß, wie man eine Art Speicherung modelliert?

triopasi

15.01.2018, 10:44

@werdas34

Einfacher denken! Nix Modulo. Wie kannst du ohne Rechnen sehen ob z.B. "1111" (4) oder "111" (3) oder "11" (2) oder "1" (1) durch 2 Teilbar ist?

werdas34

Beitragsersteller

15.01.2018, 10:46

@triopasi

Gerade bzw ungerade Anzahl an Einsen?

triopasi

15.01.2018, 10:48

@werdas34

Genau. Wie könnte man sich in einer TM merken, ob die aktuelle 1 eine "gerade" oder "ungerade Eins" ist?

werdas34

Beitragsersteller

15.01.2018, 10:51

@triopasi

Wenn sich um eine gerade Eins handelt befindet sie sich auf einem geraden Platz? Sonst fällt mir nichts ein.

triopasi

15.01.2018, 10:53

@werdas34

Zustände! Erste Eins = "ungerade Eins" = Zustand ungerade. Ist die nächste Position ne 1 ändert sich der Zusand auf "Zustand gerade" usw. Verstehste worauf ich hinaus will?

werdas34

Beitragsersteller

15.01.2018, 10:56

@triopasi

Ja. Danke. Ich überlege mir jetzt wie ich das jetzt konkret löse.

Vielen Dank. :D

triopasi

15.01.2018, 10:58

@werdas34

Gut :) Bei Fragen einfach melden.

Selbst machen bringt dir mehr als wenn dir jemand hier ne Lösung hinklatscht!

PerfectMuffin

Nutzer, der sehr aktiv auf gutefrage ist

im Thema programmieren

15.01.2018, 09:27

Du kannst das Speichern von Variablen in Zuständen modellieren.

werdas34

Beitragsersteller

15.01.2018, 10:43

@PerfectMuffin

Und wie sehe das ungefähr aus ? Hab selber schon mit allen mir möglichen, erdenklichen Tricks versucht eine Art Speicherung zu modellieren. Jedoch wie man sieht, ohne Erfolg.

KarlRanseierIII

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, programmieren, Informatik

15.01.2018, 16:34

Eine Turingmaschine kann sich nicht merken? Das wäre mir aber neu.

Am einfachsten für diesen Fall wäre wohl die Kodierung in Zuständen.

Stern -> ungerade, nächster Stern Zustand für gerade usw. usf. .

Du kannst es aber auch im Bandalphabet kodieren.

Ähnliche Beiträge

Frage i2c bus aufgaben?

aufgabe 1

1024 bit

(128 x8 bit (siehe Description))

woher kommen hier die 128 und 8 her?

aufgabe 2

8 Bausteine (000 bis 111)

warum nicht 0000 bis 1111.

...zum Beitrag

Wie erstelle ich eine Turingmaschine die sortiert?

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!

...zum Beitrag

Binärzahl in Dezimalzahl umwandeln: Woher kommt die 0000 am Anfang?

Ich lese gerade ein Buch, in dem unter anderem die Zahl 862929 in die Binärzahl umgewandelt werden soll. Soweit so gut, idR teilt man ja immer wieder durch 2 und schreibt dann jeweils Rest 0 oder Rest 1 auf.

Als Ergebnis habe ich 11010010101011010001 rausbekommen. Der Autor schreibt aber 00001101 00101010 11010001. Mir ist aufgefallen, dass das Ergebnis nahezu identisch ist, nur dass er 0000 am Anfang seines Ergebnisses einfügt, warum genau macht er das und woher weiss ich, wann ich das so handhaben muss? Theoretisch könnte man die 0000 doch auch ans Ende der Binärzahl einfügen.

Ich habe die "Vermutung", dass es daran liegt, dass im Beispiel ein 8-Bit Computer verwendet werden soll. Da ich 20 Ziffern in meinem Ergebnis habe, müsste ich die restlichen Ziffern füllen, da 20 nicht durch 8 teilbar ist, also 3*8=24, deshalb am Anfang die 0000. Ist das korrekt? Und ist mein Ergebnis in dem Fall falsch oder nur unsauber formuliert?

...zum Beitrag

Modulo rechnen: 3^444+4^333?

Hallo;

ich muss zeigen, dass 3^444+4^333 durch 5 teilbar ist. Die Regeln beherrsche ich soweit, aber in den Lösungen verstehe ich etwas einfach nicht:

(3^444 + 4333) mod 5 = ((3^4)^111 + (4^2)^166 · 4) mod 5

=􏰕(3^4 mod5)^111 mod5+((4^2 mod5)^166 ·4)mod5)􏰖mod5

=􏰕(81mod5)^111 mod5+((16mod5)^166 ·4)mod5􏰖)mod5

=(1^111 mod5+(1^166 ·4)mod5)mod5

=(1mod5 + 4mod5)mod5=

=5 mod 5=0.

Wieso wird direkt in der 1. Zeile nach ... (4^2)^166.. nochmal 4 gerechnet? Ich verstehe die Logik bzw woher das kommen soll einfach nicht.

...zum Beitrag

Prüfen ob Zahl Primzahl - Struktogramm?

Hallo,

ich wollte mal fragen ob mein Struktogramm so korrekt ist:

Meine Logik:

Eine Zahl ist ja eine PZ wenn sie nur durch sich selbst und 1 teilbar ist. Also wende ich die modulo funktion an und teste alle zahlen die zwischen 2 und der hälfte der Zahl liegen, ob ein Rest von 0 rauskommt. Kommt ein Rest von 0 raus heißt das, dass die Zahl keine Primzahl ist, da sie ja durch mind. eine weitere Zahl ausser 1 und sich selbst teilbar ist. Habe ich nun das i bis Zahl/2 hochgezählt, kann es sich bei der Zahl nurnoch um eine PZ handeln.

MFG

...zum Beitrag

Was ist eine Turingmaschine?

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

...zum Beitrag

De Morgansche Regeln?

Kann mir bitte jemand bei meinen Hausaufgaben helfen? Ich kann das alleine nicht :(

"Negieren Sie folgende Aussage formal (De Morgansche Regeln):

((x>14 ^ x<20) v (x>21 ^ x ≤34))

In Ihrem Ergebnis sollen nur mehr die logischen Operatoren UND (^) & OR (v) vorkommen (keine Negation!)"

...zum Beitrag

Kann mir jemand bei der Programmier aufgabe in C# helfen?

Schreiben Sie ein Programm, das zu einer eingegebenen Zahl im Bereich von 1...1000 ermittelt, wie oft diese Zahl ohne Rest durch 5 teilbar ist. Verwenden Sie hier für die kopfgesteuerte Wiederholung und den arithmetischen Operator Modulo (%) für die Abfrage..

...zum Beitrag

Was ist der Sinn von turingvollständigen Blockchains?

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?

...zum Beitrag

Kongruenzgleichung, Modulorechnung?

Ich sitze nun seit etwas Längerem an einer Aufgabe, bei der ich nicht einfach nicht zur richtigen Lösung komme.

So lautet die Aufgabe:

21 * x ≡ 36 (mod 51). Für das x soll 26 rauskommen, doch ich komme lediglich auf 27, egal was ich mache. Ich finde den Fehler nicht, all meine Rechnungen müssen eigentlich stimmen. Ich bin so vorgegangen:

Zuerst habe ich den ggT(51, 21) gesucht, dieser ist 3. Da der ggT 3 lautet, müssen "alle" Zahlen der Gleichung durch 3 geteilt werden - falls das b, hier die 36, durch 3 teilbar ist, kann man fortfahren - es ist durch 3 teilbar.

Ich habe dann im erw. euklidischen Algorithmus 51/3, also 17 und 21/3, also 7, eingesetzt, bin letztendlich auf den ggT von 1 gekommen und habe als y das Ergebnis 5 bekommen. Die 5 dann wieder mit der 36 multipliziert, ergibt 180, die 180 durch den eigenen Rest (Modulo 51) ersetzt, ergibt 27. Und das ist falsch.

Ich weiß nicht, ob sich hier jemand mit diesem Thema auskennt. Wenn ja - kann mir da jemand helfen? 😅

...zum Beitrag

Labyrinth Rekursiv kürzesten Pfad finden?

Habe folgende Aufgabe. Ich soll den Kürzesten Pfad in einem Labyrinth Rekursiv finden.

Bisher kenne ich mich nur mit Wave Propagation (Iterativ) und wallfollower etc aus.

Meine Idee ists nun, dass ich Rekursiv erstmal das Maze entdecke und jedem Schritt eine Distanz zu ordne (Rekursive tiefe).

Nachdem alle Zellen discovered sind gehe ich vom Ziel aus und Suche dort Rekursiv per Backtracking den Kürzesten weg.

Ist das der Richtige Ansatz um das Problem zu lösen?

Das Labyrinth kann auch keine Wände haben und sehr großen Freiraum. Siehe Beispiel:

new String[]{
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "S               D",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
}

Es wird per Aufgabe zugesichert, dass der Weg maximal 65535 schritte lang ist. Das springt sofort ins Auge, weil unsigned short so groß ist. Dies würde meine Theorie bestätigen wenn man eine unsigned short matrix nehmen würde zum tracken der besuchten Zellen.

Oder gibts da eine bessere Lösung? Hab noch nie wirklich rekursiv gearbeitet und mag Rekursion nicht wirklich bisher.

...zum Beitrag

Wie prüft man in "C", ob eine Zahl eine Primzahl ist?

/ Primzahl.c /

include include

main()

{ int zahl=16; //Zum Testen

int counter = 1; //Counter für die Schleife

int rest = 1; //Variable für den Rest (Modulo)

while (counter < (zahl-1)) //Solange counter < 15 (Also von 1 bis 14)

rest = zahl%(zahl-counter); //(16/Alle kleineren natürlichen Zahlen bis auf 1)

if (rest=0) //Ist die Zahl Restfrei durch eine kleinere natürliche Zahl teilbar, ist die Zahl keine Primzahl;

{ printf("Diese Zahl ist keine Primzahl"); }

counter++; //Counter wird um 1 erhöht und die Schleife beginnt erneut }

system("pause"); //Damit das Programm sich nach beendigung seiner Aufgabe nicht gleivh selbst auslöscht }

Das Programm funktioniert nicht. Deswegen meine Frage: Wo liegt der Fehler?

Danke im Voraus ;)

...zum Beitrag

Haskell Funktion Frage?

Wenn man eine Funktion erstellen soll, bei der die Funktion zwei Werte nimmt und prüft, ob ein Wert durch den anderen teilbar ist, wie schreibt man das in Haskell als Code?

nehmen wir an:

isDivisible -> Integer -> Integer -> Bool

Wie schaut dann der Rest aus? So?

isDivisible x % y == 0 = true else false

y % x == 0 = true else false?? Das klingt so bescheuert aber ich weiß sonst nicht wie es aussehen sollte! Kann mir da wer weiterhelfen?

Zusätzlich müsste ich dann auch eine Funktion schreiben, die so aussieht:

isPrime -> Integer -> Bool

welches eine Zahl nimmt und ausgibt ob diese eine Primzahl ist oder nicht, dafür soll ich die vorherige Funktion benutzen, jedoch komm ich da eben nicht weiter. Und bei der hier bin ich mir auch nicht sicher, wie würde da der Code aussehen?

...zum Beitrag

Typ 2 Sprache die Pumping Lemma erfüllt?

Das Pumping Lemma ist hier erfüllt. Es soll sich hier um eine kontrexfreie Sprache vom Typ 2 handeln. Woran erkenn ich dies?

...zum Beitrag

Was möchtest Du wissen?

Deinen Beitrag erstellen