Springen naar inhoud

[wiskunde] recursief/recursief opsombaar


  • Log in om te kunnen reageren

#1

Blacer

    Blacer


  • >25 berichten
  • 34 berichten
  • Gebruiker

Geplaatst op 10 april 2009 - 09:25

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 LaTeX waarbij (p,x) over de natuurlijke getallen loopt zodanig dat het programma p stopt met x als invoer (dus het getal LaTeX 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?

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Jan van de Velde

    Jan van de Velde


  • >5k berichten
  • 44893 berichten
  • Moderator

Geplaatst op 12 april 2009 - 09:29

Iemand die hier een handje kan toesteken?
ALS WIJ JE GEHOLPEN HEBBEN....
help ons dan eiwitten vouwen, en help mee ziekten als kanker en zo te bestrijden in de vrije tijd van je chip...
http://www.wetenscha...showtopic=59270





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures