---

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

---

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

---

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