|
| 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)
| |
|
|