[wiskunde] recursief/recursief opsombaar

Blacer

Ik heb de afgelopen tijd een module gevolgd op school over diophantische vergelijkingen. Aan het eind ging dit ook over het tiende probleem van Hilbert, en in verband hiermee het Stop-probleem van Turing.

Vervolgens willen ze gaan bewijzen dat er een recursief opsombare verzameling bestaat, die niet recursief is, maar daar haak ik toch echt af.

(Voor de zekerheid: een recursieve werd gedefinieerd als: er bestaat een computerprogramma dat bij de invoer van een getal n 'ja' geeft als n tot die verzameling hoort en 'nee' als n niet tot die verzameling hoort. Een recursief opsombare verzameling is de uitvoer van een eindig computerprogramma op een ideale computer)

Het probleem is als volgt:

Bekijk de verzameling S van natuurlijke getallen \( 2^p3^x\) waarbij (p,x) over de natuurlijke getallen loopt zodanig dat het programma p stopt met x als invoer (dus het getal \( 2^p3^x\) zit in S precies als het programma p stopt met invoer x).

Volgens de stelling van Turing bestaat er geen programma, dat van een ander programma kan zeggen of het stopt met een bepaalde invoer, dus ik begrijp nog wel dat de verzameling S niet recursief is. Maar volgens het boekje is het wel recursief opsombaar, maar hoe kun je dat dan bewijzen, je kunt er immers niet achter komen wat p en x zijn?

Jan van de Velde

Iemand die hier een handje kan toesteken?

Wetenschapsforum

Laatste berichten

Nieuwsberichten

[wiskunde] recursief/recursief opsombaar

[wiskunde] recursief/recursief opsombaar

Re: [wiskunde] recursief/recursief opsombaar