| Zeige Beiträge 1 bis 7 von 7 Treffern |
|
 Thema: semi-entscheidbarkeit |
|
|
ich möchte zeigen ,dass weder das äquivalenzproblem EQ für DTM semi-entscheidbar ist noch das Komplement von EQ.
EQ={<code(A),code(B)>/ A1 und A2 ist DTM und L(A1)=L(A2)}.
ich sollte dazu die Reduktion und komplement des Haltproblems verwenden.
Meine Beweisideen:
ich zeige dass ,
1)Komplement(HP)<= Komplement(EQ) ist
2)Komplement (HP)<=EQ ist
und daraus folgt ,dass weder EQ noch Komplement(EQ) semi-entscheidbar ist.
Bitte Hilfe beim umsetzen,da ich nicht weiß wie ich das ganze beweisen kann.
ich weiß, dass HP semi entscheidbar ist und dass Komplement(HP) ist es auch.
herzlich
ps:<= bedeutet kleiner gleich
|
|
| Thema: Loop-Programme von Funktionen |
bradig
| Antworten: |
14 |
| Hits: |
10.933 |
|
|
jetzt soll ich das gleiche mit der Funtion div tun.
ich überlege mir gerade,wie ich das am bestens machen kann
|
|
| Thema: while -programm einer rekursive Funktion(berechenbarkeit ) |
|
|
ich habe eine partielle Funktion f: IN*IN---->IN mit
1 falls x größer gleich 1 und x teilt y
f(x,y)={0 falls x größer gleich 1 und x teilt y nicht
undefiniert sonst
f ist bei{0}*IN undefiniert.
a)wie kann ich ein while -programm angeben,dass f berechnet
b)wie kann ich f als u-rekursive Funktion angeben
seit gestern komme ich nicht weiter bei der Aufgabe.
Bitte Hilfe
Bradig
|
|
| Thema: Loop-Programme von Funktionen |
bradig
| Antworten: |
14 |
| Hits: |
10.933 |
|
|
Loop-Programm (berechenbarkeit theoretische informatik)
besipiel add: IN*IN--->IN
mit add(x,y)=x+y
die Funktion add ist Loop-berechenbar,weil sie sich durch ein Loop-Programm berechnet lässt.
Resultat xo=x+y
Loop-Programm für die Funktion add:
xo=x+0;
Loop yDo
xo=x+1;
End
|
|
| Thema: Loop-Programme von Funktionen |
bradig
| Antworten: |
14 |
| Hits: |
10.933 |
|
|
c)ich soll ein Loop-Programm für folgende Funktion geben:
div: !N^2 ------> !N
o falls x=0 oder (x>0 und x teilt y nicht)
div(x,y)={
1 falls x>0 und x teilt y
also mit Addition und Multiplikation habe ich schon gemacht aber das kriege ich seit gestern nicht hin.
Bitte Hilfe
herzlich
Bradig
|
|
|
| Zeige Beiträge 1 bis 7 von 7 Treffern |
|
|
|
