schultz
unregistriert
 |
|
| Turingmaschine quadrieren |
     |
Hallo Community.
Ich soll eine Turingmaschine konstruieren, die die Funktion f(x)=x^2 simuliert.
D.h wenn ich habe eingaben der form 111 für 3 zum Beispiel und die ausgabe wäre in diesem Fall dann 111111111.
nun weiß ich nicht so recht wie ich das bewerkstellen soll. ich hatte die idee, für jede 1 soviel einsen zu schreiben wie insgesamt vorhanden sind und dann die 1 zu löschen und so weiter. leider weiß ich nicht so ganz wie ich das hinkriegen soll.
hoffe auf hilfreiche antworten
mfg schultz
|
|
24.05.2011 18:11 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Wenn du deine Eingabe nicht binär kodierst wäre es m.E. günstiger für deine Eingabewörter keine Einsen zu verwenden.
Ich denke auch du kommst besser wenn du die Eingabe binär kodierst oder ist das in der Aufgabenstellung anders gefordert?
Für die binäre Kodierung schau dir die schriftliche Addition von binärzahlen an, dann kannst du damit eine Turingmaschine erstellen, welche das bewerkstelligt.
VG,
Karlito
|
|
|
27.05.2011 17:46 |
|
|
schultz
unregistriert
|
|
nein die eingabe erfolgt wie gesagt als eine folge von einsen...ist halt von der aufgabenstellung her so gewählt.hast du dazu auch einen ansatz?
|
|
|
27.05.2011 21:47 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Naja, einfach die schrifliche unäre Multiplikation anschauen 
D.h. wie bei der normalen Multipliation die Zahlen versetzt untereinanderschreiben und dann "addieren". Wobei hier jede einzelne eins in der "treppe" eine eins im ergebnis ist.
Ohne nachzudenken, ob das jetzt elegant ist:
Die Eingabe kopieren (hinter ein Trennzeichen), dann Zustand wechseln in "Rechenzustand", dann Ergebnis hinter weiterem trennzeichen berechnen, indem du das eingabewort hinter die Kopie schreibst, dann von der Kopie immer ein zeichen wegstreichst und dann das eingabewort solange an dein ergebnis anhängst, bis die kopie verschwunden ist...
Je nach aufgabenstellung dann noch aufräumen...
Also exemplarisch an 111² (b= blank, # = trennzeichen):
1. Eingabewort kopieren:
b111b -> b111#111b
2. kopieren bis kopie aufgebraucht
b111#111b ->
b111#11##111b ->
b111#1###111111b ->
b111#####111111111b
Sollte vom ablauf her funktionieren...
VG,
Karlito
|
|
|
28.05.2011 22:47 |
|
|
|
