Overleg:Stopprobleem

De tekst van het artikel beschrijft het Halting- of Stop-probleem. Een beslissingsprobleem is iets veel algemeners. (Hoewel het stopprobleem idd een voorbeeld is van een beslissingsprobleem.) JorisVR

Ik denk dat "beslisbaarheid" bedoeld is.Madyno 24 jun 2007 23:40 (CEST)

De inhoud van dit artikel gaat duidelijk over het Halting probleem. Volgens mij is stopprobleem de beste vertaling, dus: rename. Er is overigens een ander artikel over "berekenbaarheid". JorisVR 4 jul 2007 00:08 (CEST)

Halt

Het is niet mijn terrein, maar de sectie "Bewijs van onberekenbaarheid" doet mij sterk aan de Russel-paradox denken. Wel begrijp ik hier niet erg hoe het algoritme A op zichzelf kan worden toegepast. Madyno (overleg) 11 nov 2020 12:06 (CET)

Dat het bewijs je erg aan de Russelparadox doet denken is niet zo verwonderlijk. Ze gebruiken beide een techniek die diagonalisering wordt genoemd, en het is heel aannemelijk dat Turing zich door de Russelparadox liet inspireren. Hoopje (overleg) 11 nov 2020 14:15 (CET)

Vermoedelijk - maar dat zal bijna niemand erin lezen - gaat het om programma's en inputs die voorgesteld worden als rijtjes symbolen bv 0 en 1. Of vergis ik me? Madyno (overleg) 11 nov 2020 12:13 (CET)

Het is inderdaad niet zo duidelijk in de tekst. In principe berekenen turingmachines functies op natuurlijke getallen. De invoer is dus een natuurlijk getal, dat eerst als turingmachine geinterpreteerd moet worden (het is een soort gödelnummer, zeg maar). Als je het wat moderner wil formuleren, en toch het verschil tussen het object zelf en zijn beschrijving duidelijk wil maken, zou je over "broncode" kunnen praten. De vraag is, termineert het programma 'paradox' als hij zijn eigen broncode als invoer krijgt. Hoopje (overleg) 11 nov 2020 14:15 (CET)

Mogelijk

Volgens mij gaat het 'stopprobleem' niet om te bepalen of een algoritme bij een bepaalde input eindig, dan wel oneindig is, maar of er een procedure is die voor willekeurig algoritmen en input bepaalt of het algoritne eindig dan wel oneindig is, dwz of dat mogelijk is. Madyno (overleg) 12 nov 2020 18:04 (CET)

Een "probleem" in deze context verwijst naar een beslissingsprobleem, d.w.z. een bepaalde vraagstelling die je me "ja" of "nee" kunt beantwoorden. In de berekenbaarheids- en complexiteitstheorie worden er algoritmes gezocht die bepaalde problemen oplossen. Het stopprobleem is een zogenaamd onbeslisbaar probleem, wat wil zeggen dat er geen algoritme bestaat dat het probleem oplost. Er bestaan ook problemen waarvoor wél algoritmes bestaan, bijvoorbeeld het vervulbaarheidsprobleem. Hoopje (overleg) 12 nov 2020 18:40 (CET)

Hoopje, ik doe nog even een poging. 1. Hoe bepaal ik of een natuurlijk getal even is. 2. Is het mogelijk te bepalen of een natuurlijk getal even is. 1 vraagt naar een algoritme, 2 of zo'n algoritme überhaupt bestaat. 1 is duidelijk een beslissingsprobleem, maar 2? Het komt mij voor dat het stopprobleem van het type 2 is. Kun je commentaar geven? Madyno (overleg) 13 nov 2020 11:06 (CET)

Het stopprobleem is ook van "type 1". Anders zou de zin "Het is een bekend voorbeeld van een wiskundig probleem dat onbeslisbaar is", die ook in het artikel staat, ook geen zin hebben, want "beslisbaar" is een mogelijke eigenschap van beslissingsproblemen. Kortom: het stopprobleem is een beslissingsprobleem, het stopprobleem is niet de vraag of het stopprobleem beslisbaar is. Hoopje (overleg) 13 nov 2020 11:30 (CET)

Ik ben niet erg overtuigd.

Probleem 11 is hoe te bepalen of het algoritme A bij de eindige input x eindig is of oneindig.

Probleem 12 is hoe te bepalen of het algoritme A bij elke eindige input x eindig is of oneindig.

Probleem 13 is hoe te bepalen of elk algoritme A bij de eindige input x eindig is of oneindig.

Probleem 14 is hoe te bepalen of elk algoritme A bij elke eindige input x eindig is of oneindig.

Probleem 21 is of het algoritme A bij de eindige input x eindig is of oneindig.

Probleem 22 is of het algoritme A bij elke eindige input x eindig is of oneindig.

Probleem 23 is of elk algoritme A bij de eindige input x eindig is of oneindig.

Probleem 24 is of elk algoritme A bij elke eindige input x eindig is of oneindig.

Ik heb het idee dat het bewijs voor probleem 24 gegeven wordt. Er wordt immers een conclusie getrokken over paradox(paradox), een ander algoritme dan het aanvankelijk A. Madyno (overleg) 13 nov 2020 16:16 (CET)

De Duitse Wikipedia: Het stopprobleem beschrijft de vraag of de uitvoering van een algoritme succesvol is. Hoewel dit voor veel algoritmen gemakkelijk kan worden beantwoord, heeft de wiskundige Alan Turing kunnen bewijzen dat er geen algoritme is dat deze vraag beantwoordt voor alle mogelijke algoritmen en eventuele invoer.

Volgens mij dus de vraag of iets mogelijk is. Madyno (overleg) 13 nov 2020 16:20 (CET)

Je haalt dingen door elkaar. Ten eerste is er het beslissingsprobleem. In de standaardvariant luidt dat: gegeven een programma A en invoer X, bepaal of het prgramma A bij invoer X stopt. De naam van dat beslissingsprobleem is "Stopprobleem". Dat is gewoon een definitie, en dat staat ook zo in de Duitse Wikipedia ("Das Halteproblem beschreibt die Frage, ob die Ausführung eines Algorithmus zu einem Ende gelangt.", ofwel "Het stopprobleem beschrijft de vraag of de uitvoering van een algoritme een einde heeft.") Het staat ook zo in de Engelse Wikipedia ("[...] The halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running [...]."), en in de Franse.

Vervolgens is de vraag: bestaat er een algoritme dat dit Stopprobleem oplost? Het antwoord op die vraag (en dat is door Turing bewezen) is: Nee, er bestaat geen algoritme dat het Stopprobleem oplost. Maar die vraag of het mogelijk is het Stopprobleem op te lossen, dat is niet het Stopprobleem, dat gaat over het Stopprobleem.

Hoopje (overleg) 13 nov 2020 16:54 (CET)

Duidelijk. Madyno (overleg) 13 nov 2020 18:18 (CET)