/ Forside / Karriere / Uddannelse / Højere uddannelser / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Højere uddannelser
#NavnPoint
Nordsted1 1588
erling_l 1224
ans 1150
dova 895
gert_h 800
molokyle 661
berpox 610
creamygirl 610
3773 570
10  jomfruane 570
Uafgørlig = rekursiv enumerable (og
Fra : Preben Holm


Dato : 13-01-05 17:25

Hej alle


Jeg er stødt på ovenstående problem. Min konklusion er blevet at
"uafgørlighed" ikke medfører at noget er rekursivt enumerabelt!

Men at rekursivt enumerabelt (og ikke rekursiv) medfører at det er
uafgørligt!


Er det korrekt, eller er jeg helt galt på den!


Følgende skulle man vist gerne kunne sætte lig hinanden:

rekursivt = afgørligt
rekursivt enumerabelt = turing-genkendeligt =



Med venlig hilsen
Preben Holm

 
 
Torben Ægidius Mogen~ (13-01-2005)
Kommentar
Fra : Torben Ægidius Mogen~


Dato : 13-01-05 18:09

Preben Holm <64bitNOnoSPAMno@mailme.dk> writes:


> Følgende skulle man vist gerne kunne sætte lig hinanden:
>
> rekursivt = afgørligt

Ja.

> rekursivt enumerabelt = turing-genkendeligt

Nej, rekursivt enumerabelt = semiafgørligt. Det betyder, at hvis
udsagnet er sandt (elementet findes i mængden), så findes der et bevis
for dette, men hvis det er falsk findes der ikke nødvendigvis et
modbevis.

Turing-genkendelighed indebærer, at en terminerende Turingmaskine kan
afgøre om et element findes i mængden. Semiafgørlighed betyder at
Turingmaskinen kan være ikke-terminerende for elementer i
komplementærmængden.

Torben

Preben Holm (14-01-2005)
Kommentar
Fra : Preben Holm


Dato : 14-01-05 20:09

>>Følgende skulle man vist gerne kunne sætte lig hinanden:
>>
>> rekursivt = afgørligt
>
>
> Ja.
>
>
>> rekursivt enumerabelt = turing-genkendeligt
>
>
> Nej, rekursivt enumerabelt = semiafgørligt. Det betyder, at hvis
> udsagnet er sandt (elementet findes i mængden), så findes der et bevis
> for dette, men hvis det er falsk findes der ikke nødvendigvis et
> modbevis.
>
> Turing-genkendelighed indebærer, at en terminerende Turingmaskine kan
> afgøre om et element findes i mængden. Semiafgørlighed betyder at
> Turingmaskinen kan være ikke-terminerende for elementer i
> komplementærmængden.

Nope, du snakker om Turing-afgørlig og ikke Turing-genkendelig!
(det skal dog siges, at der er mange definitioner på området - måske
de ikke er enige, men min lærebog skelner mellem Turing-genkendelig
(måske loopende), og Turing-afgørligt)

Søg
Reklame
Statistik
Spørgsmål : 177552
Tips : 31968
Nyheder : 719565
Indlæg : 6408847
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste