TM: Summe der n-ten Zahlen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | A1.) Sei [mm] $\varphi [/mm] : [mm] \IN_0 \rightarrow \IN_0: [/mm] x [mm] \mapsto \sum\limits_{i = 0}^x [/mm] i$ eine Funktion. Konstruieren Sie eine (zusammegesetzte) Turingmaschine, welche f berechnet und begründen Sie ihre Antwort. |
Hallo zusammen,
ich stehe gerade ein bisschen auf dem Schlauch bei dieser Aufgabe und zwar ist mein einziger Ansatz irgendwie der kleine Gauß, bloß dann gestaltet sich mein Ansatz als langwierig (v.a. später bei der ganzzahligen Division durch 2) und deswegen wollte ich fragen ob es vllt. einen einfacheren Ansatz gibt.
Grüße
Joe
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:55 Mo 24.06.2013 | | Autor: | felixf |
Moin Joe,
> A1.) Sei [mm]\varphi : \IN_0 \rightarrow \IN_0: x \mapsto \sum\limits_{i = 0}^x i[/mm]
> eine Funktion. Konstruieren Sie eine (zusammegesetzte)
> Turingmaschine, welche f berechnet und begründen Sie ihre
> Antwort.
>
> ich stehe gerade ein bisschen auf dem Schlauch bei dieser
> Aufgabe und zwar ist mein einziger Ansatz irgendwie der
> kleine Gauß, bloß dann gestaltet sich mein Ansatz als
> langwierig (v.a. später bei der ganzzahligen Division
> durch 2) und deswegen wollte ich fragen ob es vllt. einen
> einfacheren Ansatz gibt.
wenn du die Zahlen als binaere Strings darstellst, ist das Teilen durch 2 sehr einfach: du streichst einfach die letzte Stelle (bzw. erste Stelle, je nachdem welche die Einserstelle ist) weg.
LG Felix
|
|
|
| |
|
Hallo Felix, das habe ich vergessen zu erwähnen - die Zahlen sind unär, sprich in Strichen kodiert.
Grüße
Joe
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:09 Mo 24.06.2013 | | Autor: | felixf |
Moin Joe,
> Hallo Felix, das habe ich vergessen zu erwähnen - die
> Zahlen sind unär, sprich in Strichen kodiert.
in dem Fall ist es aber auch nicht sooo schwer, streiche jeden zweiten Strich weg, und dann schiebe die Striche wieder zusammen. Ist etwas muehselig das zu machen, aber durchaus moeglich. Und soo kompliziert sollte es nicht sein, eine eigene TM fuer genau diesen Zweck zu machen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Di 25.06.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
