Turing Maschine Befehlsliste?

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?

Bild zum Beitrag

1 Antwort

Vom Beitragsersteller als hilfreich ausgezeichnet

CyborgBeta

12.01.2024, 11:19

Hallo, das ginge so:

//-------CONFIGURATION
name: Schiebe erste 1 nach rechts
init: q0
accept: q5

q0,0
q0,0,>

q0,1
q1,1,>

// End state
q0,_
q5,_,-

q1,1
q1,1,>

q1,0
q2,0,<

// End state
q1,_
q5,_,-

q2,1
q2,1,<

q2,0
q3,0,>

q2,_
q3,_,>

q3,0
q3,0,>

q3,1
q4,0,>

q4,1
q4,1,>

// End state
q4,0
q5,1,-

Du kannst es zum Beispiel hier ausprobieren: https://turingmachinesimulator.com/ und solltest noch weitere Kommentare hinzufügen...

Woher ich das weiß:Studium / Ausbildung

maria1811

Beitragsersteller

12.01.2024, 17:22

Hallo, vielen Dank für deine Antwort. Das hilft mir sehr weiter. Wie sind die Aktionen mit >\< zu lesen? Stehen diese für Rechts oder links? Und da wo end state steht stoppt die Turing Maschine oder?

CyborgBeta

13.01.2024, 19:14

@maria1811

beides richtig, ja

Ähnliche Beiträge

Unentscheidbarkeit dieser Sprache durch Reduktion zeigen?

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!

...zum Beitrag

Wie schreibe ich eine Turingmaschine, die eine Zahl nach rechts verschiebt?

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?

...zum Beitrag

entscheidbarkeit turing-maschine konstruieren?

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?

...zum Beitrag

Alan Turing als Vorbild der LGBTQ-Bewegung?

Ist Alan Turing wirklich die Galionsfigur der LGBTQ-Bewegung?

Das hat ein Kommiliton gesagt,als er die Turing-Maschine ansprach.

...zum Beitrag

Optimaler Suchbaum Eigenschaften prüfen?

Hallo, ich habe folgende Aufgabe:

Gegeben sei der folgende Suchbaum, in dem die Elemente A;B;C;D;E

lexikographisch geordnet sind. Beweisen oder widerlegen Sie:

Der Baum kann ein optimaler Suchbaum mit 2,1 erwarteten Vergleichen sein.

Da kommen ich und viele andere nicht weiter, die meisten neigen zur Meinung, dass die Aussage falsch ist. Wir haben dazu sehr viele Gleichungen aufgestellt, die aber kompliziert zu lösen scheinen: (a bis e sind die jew. Zugriffswahrscheinlichkeiten)

a+b+c+d+e=1

a+2b+4c+3d+4e=2,1

Durch die e_ij Tabellen (erwartete Anzahl Vergleiche im Unterbaum von i bis j):

b<=a, e<=d<=c

Aber ich stecke jetzt fest wie ich hier wirklich weiterkomme. Muss ich etwa noch mehr Ungleichungen/Gleichungen aufstellen?

Vielen Dank im Voraus!

...zum Beitrag

Wie schreibe ich ein Turingprogramm ababab?

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.

...zum Beitrag

Kann ChatGPT den Turing-Test bestehen?

Mit dem später sogenannten Turing-Test formulierte Alan Turing im Jahr 1950 eine Idee, wie man feststellen könnte, ob ein Computer, also eine Maschine, ein dem Menschen gleichwertiges Denkvermögen hätte.

Testablauf

Im Zuge dieses Tests führt ein menschlicher Fragesteller, über eine Tastatur und einen Bildschirm, ohne Sicht- und Hörkontakt, eine Unterhaltung mit zwei ihm unbekannten Gesprächspartnern. Der eine Gesprächspartner ist ein Mensch, der andere eine Maschine. Kann der Fragesteller nach der intensiven Befragung nicht sagen, welcher von beiden die Maschine ist, hat die Maschine den Turing-Test bestanden und es wird der Maschine ein dem Menschen ebenbürtiges Denkvermögen unterstellt.

https://de.wikipedia.org/wiki/Turing-Test

...zum Beitrag

Turing-Maschine platzbeschränkt, zeitbeschränkt?

Ist eine platzbeschränkte Turing-Maschine immer zeitbeschränkt?
Ist eine zeitbeschränkte Turing-Maschine immer platzbeschränkt?

...zum Beitrag

Warum verwendet man offenes Hashing?

Hi,

ich bin zwar in der Lage, beide Arten Hashing und verschiedene Kollisionsbehandlungen von Hand anzuwenden, aber um zu begründen, wann offenes Hashing besser ist als geschlossenes fehlt mir noch der Realbezug zu Beispielen mit riesen Mengen von Elementen, großen Tabellen usw.

Ich weiß, dass bei dynamischen Anwendungen immer offenes gewählt wird, da die Anzahl Elemente nicht von vornherein bei diesen klar ist. Ich weiß auch, dass der Belegungsgrad der Tabelle bei geschlossenem 60% nicht überschreiten sollte. Ich nehme an, wir wollen bei geschlossenem Hashing keine großen Mengen von Elementen haben, da wir dass bei dynamischen Anwendungen aber vorher nicht wissen, nehmen wir zur Vorsicht offenes (Annahme richtig?). Aber warum kann geschlossenes Hashing mit vielen Elementen nicht umgehen? Würde dann der Aufwand viel zu groß werden, wenn dementsprechend mehr Kollisionen auftreten? Fällt jemandem noch eine Begründung ein, so diese überhaupt zutrifft?

Ich weiß außerdem, dass wir bei geschlossenem Hashing bevorzugen, später keine oder wenige Elemente wieder löschen zu müssen. Warum ist der Aufwand bei offenem Hashing da geringer?

Danke für eure Hilfe schon mal im Vorraus

...zum Beitrag

Höhe/Tiefe von Bäumen Infromatik?

ich hab auf Wikipedia gelesen, das bei Bäumen man mit der Definition der Höhe spielen kann. In den Folien meines Professor steht, dass die Höhe die Tiefe +1 ist.
D.h. ein nur eine Wurzel hat die Höhe 1. Und ein leerer die Höhe 0. auf Wikipedia hingegen steht ebenfalls, dass einige Autoren die Höhe mit der maximalen Tiefe gleich setzen.

Ich würde gern wissen, welchen Vorteil, das eine dem anderen gegenüber hat. Denn auf Wikipedia hab ich das nicht ganz verstanden , wäre nett, wenn’s einer kurz und einfacher erklären könnte beziehungsweise ganz simpel

...zum Beitrag

Könnte mir das bitte jemand erklären und gegebenenfalls die Aufgabe lösen, damit ich schauen kann, ob ich alles verstanden habe?

Ich war in der letzten Mathestunde aufgrund einer schulischen Verpflichtung nicht anwesend und dabei hat mein Kurs ein neues Thema angefangen. Im digitalen Kursheft steht jetzt die Aufgabe, die ich bis zur nächsten Stunde machen muss. Ich verstehe dabei nicht mal einen Ansatz. Könnte mir das bitte jemand erklären und gegebenenfalls die Aufgabe lösen, damit ich schauen kann, ob ich alles verstanden habe?

Das ist der genaue Wortlaut der Aufgabe :

Gegeben ist die Funktion f mit f (x) = x^4 – 2x^2. Geben Sie einen Term für die Funktion g an und zeichnen Sie beide Graphen in ein gemeinsames Koordinatensystem.

a) Man erhält den Graphen von g, indem man den Graphen von f mit dem Faktor 2 in y-Richtung streckt und um eine Einheit nach unten verschiebt.

b) Man erhält den Graphen von g, indem man den Graphen von f an der x-Achse spiegelt und um eine Einheit nach rechts verschiebt.

Dankeschön!

...zum Beitrag

Korrektheitsbeweis Algorithmus?

Hallo liebe Community,

ich habe eine Aufgabe bekommen in welcher ich Pseudocode entwickeln soll. Meinem Algorithmus wird ein Array an Zahlen gegeben A[1, n] mit n Einträgen. Ich soll in diesem Array die Senken zählen. Eine Senke ist dabei eine Position i [2, n - 1] für die folgendes gilt: A[i - 1] > A[i] < A[i + 1].

Meiner Auffasung nach bedeutet das nun, dass z.B. das Array [1, 3, 2, 4, 3, 5] zwei Senken hat. Nämlich einmal der dritte Eintrag und der fünfte Eintrag.

Mein Pseudocode sieht folgendermaßen aus:

Input: A[1, n] mit n Einträgen
Output: Anzahl der Senken

counter := 0
for j := 2 to n - 1 do
  val := A[j]
  if val < A[j - 1] and val > A[j + 1] do
    counter := counter + 1

Mein Java Code dazu sieht folgendermaßen aus:

public static int countSenken(int[] arr) {
  int counter = 0;
  for (int i = 1; i < arr.length - 1; i++) {
    int val = arr[i];
    if (val < arr[i - 1] && val < arr[i + 1]) {
      counter++;
    }
  }
}

Nun soll ich die Korrektheit meines Algorithmus' beweisen. Wir haben das schonmal an dem Beispiel des Insertionsort Algorithmus' gemacht. Die herangehensweise ist ja eigentlich, dass man eine Schleifeninvariante aufstellt und diese dann mittels Induktion beweist. Mein Problem ist jetzt aber, dass ich diese Schleifeninvariante nicht aufstellen kann. Beim Insertionsort, da beweist man ja die Sortiertheit und da verändert sich ja das Array. Aber bei diesem Algorithmus jetzt da verändert sich das Array ja gar nicht.

Ich weiß halt, dass n >= 3 sein muss damit der Algorithmus überhaupt funktioniert. Kann mir vielleicht jemand einen Ansatz geben wie ich die Korrektheit beweise?

Ich wäre euch allen sehr dankbar :)

...zum Beitrag

Was bedeutet, einen AVL-Baum "sukzessive" Aufbauen?

Wenn folgende Aufgabe gegeben ist:

Bedeutet das, dass 80 die Wurzel sein muss? Muss ich die Werte in bestimmter Reihenfolge in den Baum eintragen, solange ich die Sortierung nach Größe einhalte?

Oder kann ich mit einer Wurzel wie 50 starten, was das ganze mit den Rotationen vermutlich etwas abkürzt?

Danke für eure Hilfe

...zum Beitrag

Wortproblem Typ 1 ist NP-schwer kann ma es per Turing Maschine berechnen?

Das Wortproblem Typ 1 für kontextsensitive Sprachen ist entscheidbar.

Bzgl. der Komplexität ist es NP-schwierig.

O(k^n) Komplexität

Laut der Folie kann man nicht zeigen, dass es in NP liegt. Es ist NP-schwierig.

Nun meine Frage: Ist das Wortproblem Typ 1 Turing-Maschinen berechenbar? Ja oder Nein, wenn es wie hier angegeben NP-schwierig ist?
Es gilt P Teilmenge von NP.

...zum Beitrag

Was möchtest Du wissen?

Deine Frage stellen