simulation abstrakter machinen < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:30 Sa 04.11.2006 | | Autor: | AriR |
| Aufgabe | | Geben Sie eine Simulation einer Turingmaschine über dem Alphabet [mm] \{*_1;*_2\} [/mm] auf einer Turingmaschine über dem Alphabet [mm] \{*\} [/mm] an. |
(Frage zuvor nicht gestellt)
Hey leute,
so wie ich die aufgabe verstehe muss ich übergangsfunktionen finden, so dass ich die Turing Machine mit dem 2-elmentigen Alphabet auf dem einelementigen darstellen kann. Wir haben in der Vorlesung die In und Out funktion der einelementigen Turing M. definiert, aber nicht die für die 2-elementige.
also bei der TM mit dem 1elemntigen Alphabet haben wir n-tupel von sternen getrennt durch blanks genommen, um verschiedene natürlich zahlen darzustellen, nur was macht man jetzt, wenn man ein weiteres symbol hat? man hat ja keine ahnung welche bedeutung das haben soll. es kann ja sein, dass das 2te symbol für ein vorzeichen steht oder gar keine besodneres bedeutung hat.
kann man das irgendwie der aufgabe ablesen?
bin dankbar für jede hilfe
Gruß Ari
|
|
| |
|
Moin Ari,
konstruier doch mal als Warming Up eine Injektion [mm] \IN\times\IN\to \IN.
[/mm]
Und dann überleg mal, warum Dir das dann bei Deiner Aufgabe unmittelbar weiterhilft.
Gruss,
Mathias
|
|
|
|
