Overleg:Beslissingsprobleem

Ja/nee

Ik denk dat een beslissingsprobleem niet per se een antwoord ja of nee dient te hebben. Het zal wel zo geformuleerd kunnen worden. Over het algemeen zal het gaan om de keuze. uit een alternatief. Of kan het ook nog ruimer, Bv. welke van A1,..., An is de grootste? Madyno (overleg) 10 aug 2022 12:01 (CEST)

Volgens de eerste zin gaat het hier over een beslissingsprobleem in de complexiteitstheorie, en daar dient een beslissingsprobleem wel degelijk "per se een antwoord ja of nee" te hebben. Hoopje (overleg) 10 aug 2022 17:02 (CEST)

Dat kan worden ondervangen door de eerste zin te veranderen. Ik heb al eens als eerste zin geschreven: Een beslissingsprobleem wordt gedefinieerd als een probleem waar, bij een bepaalde, gegeven invoer een bevestigend of ontkennend antwoord op moet worden gegeven. Ik ben het met Madyno eens. Een Markov beslissingsketen bestaat uit een aaneenschakeling van beslissingsproblemen, die niet per sé binair zijn. Deze keten wordt toch als een beslissingsprobleem gezien. Dat is de achtergrond van de titel die Hoopje pardoes heeft weggehaald, terwijl de inhoud ervan wel in het kader van het artikel paste. ChristiaanPR (overleg) 10 aug 2022 20:22 (CEST)

Nogmaals, het gaat hier over het begrip "beslissingsprobleem" zoals dat in berekenbaarheids- en complexiteitstheorie gebruikt wordt. Dat begrip neemt binnen dat gebied een vrij centrale plaats in. Dat kan je niet zomaar even anders definieren, want dan werken de normale definities van "(polynomiale) reductie" en "NP-volledig" niet meer. Je hoeft me trouwens niet op mijn woord te geloven. Je kan ook gewoon even de gelinkte Engelse of Duitse Wikipediapagina's bekijken, of een willekeurig boek over het onderwerp uit je boekenkast trekken.

Een "Markov beslissingsprobleem" is geen beslissingsprobleem maar (de invoer van) een optimalisatieprobleem (een andere naam ervoor is dan ook Markov beslissingsproces). Nu kun je elk optimalisatieprobleem ook als beslissingsprobleem opvatten (in plaats "Wat is de beste oplossing" vraag je "Bestaat er een oplossing die beter is dan waarde x?"). maar dat Markov beslissingsproces komt uit een ander deelgebied van de informatica waar men in andere dingen geinteresseerd is. Je moet dus niet denken dat een willekeurig opgegoogled veertig jaar oud rapportje goede literatuur over het onderwerp "beslissingsprobleem" is alleen maar omdat er "belissingsprobleem" in de titel voorkomt.

Het kan natuurlijk best zijn dat er andere betekenissen van "beslissingsprobleem" bestaan. Ik kan me zelfs voorstellen dat die ook een eigen artikel verdienen. (Over dat Markov beslissingsprobleem/-proces hebben we bijvoorbeeld nog niks.) Ik zou zeggen: voel je vrij en ga je gang. (Als je tenminste over goede bronnen beschikt, en die ook begrijpt.) Hoopje (overleg) 10 aug 2022 21:28 (CEST)

En PS. Ik heb je twee bewerkingen weer teruggedraaid, en wel om de volgende redenen:

• Dat artikel is niet relevant (zie boven).
• Je klaagt over foute zinnen, en dan produceer je zinsdelen als "dat met bevestigend of ontkennend beantwoord dient te worden". Dat "bevestigend" en "ontkennend" vind ik overigens ook vooral duur Nederlands voor het veel duidelijkere "ja" en "nee", maar goed, over smaak valt niet te twisten.
• Wat je met de laatste alinea wilt begrijp ik nog steeds niet. Beslissingsproblemen worden vaak aan de hand van de verzameling positieve vraagstellingen gedefinieerd. De reden daarvoor is dat ze dan heel natuurlijk een plaats innemen in de formeletalentheorie (in de Chomskyhierarchie bijvoorbeeld). Het is dus niet zo dat je die verzameling aan de hand van het probleem bepaalt, zoals jij, als ik je bewerking goed begrijp, lijkt te denken.

Hoopje (overleg) 10 aug 2022 21:40 (CEST)

NB Het kan zijn dat literatuur ontbreekt, maar missen (of misten) doet het niet. Wat zou literatuur trouwens geraakt moeten hebben? Nu even over ja/nee. De Engelse W. zegt dat een beslissingsprobleem zo geherformuleerd kan worden dat het een ja/nee antwoord verlangt. Madyno (overleg) 11 aug 2022 00:49 (CEST)

Door het beslissingsprobleem "is het getal $n$ een priemgetal?" te definiëren als de oneindige verzameling $\{2,3,5,7,11,...\}$ definieer je alleen maar iets dat al is gedefinieerd. ChristiaanPR (overleg) 11 aug 2022 06:15 (CEST)

Definitie

Mij komt het nogal onduidelijk voor. De argumentatie bij het voorbeeld over een priemgetal is beslist onvoldoende. De vraag: "is mijn buurman gay?" heeft ook als antwoord ja of nee, maar is nog geen beslissingsprobleem. En dan: wat zijn computationele problemen? Als een beslissingsprobleem onbeslisbaar is, bestaat er geen algoritme voor de oplossing. Mar wat is dan de betekenis dat het onbeslisbare probleem computationeel is? Madyno (overleg) 11 aug 2022 10:11 (CEST)

De Duitse W. zegt wat anders. Niet de vraag of de invoer een bepaalde eigenschap heeft, is het beslissingsprobleem, maar of er een algoritme bestaat dat de vraag beantwoordt. In het geval van de priemgetallen zou het beslissingsprobleem zijn: Is er een algoritme om uit te maken of een getal een priemgetal is? Ja, dat is er, dus het probleem is beslisbaar. Maar dat is ook onbevredigend, want het beslisbare zit in de beantwoording van de vraag of een bepaald getal priem is. Madyno (overleg) 11 aug 2022 10:39 (CEST)

Op de Duitse wikipedia is "Entscheidbarkeitsproblem" blijkbaar sinds twee jaar een doorverwijzing naar "Entscheidbar", wat met de Nederlandse pagina Recursieve verzameling verbonden is. "Entscheidbar" betekent "beslisbaar", niet "beslissingsprobleem". Een beslissingsprobleem hoeft niet beslisbaar te zijn, bijvoorbeeld het stopprobleem.

Wat je met je "is mijn buurman gay"-voorbeeld probeert aan te tonen is me een raadsel. We doen hier nog altijd wiskunde. Je kunt het ook over een verzameling buurmannen hebben, maar heb je daarmee aangetoond dat "verzameling" een onduidelijk begrip is? Hoopje (overleg) 11 aug 2022 15:07 (CEST)

1. Het voorbeeld met de buurman is analoog aan het voorbeeld met de priemgetallen. In het artikel staat dat dat een beslissingsprobleem is omdat het een ja/nee vraag is. Dat is de vraag over mijn. uurman ook.

2. Voor een niet-beslisbaar beslissingsprobleem bestaat geen algoritme dat in eindig stappen tot het antwoord leidt. Wat is het computationele daaraan? Madyno (overleg) 11 aug 2022 16:26 (CEST)

Ik heb de tekst niet geschreven, maar in de eerste zin hoeft wat mij betreft niet al een hele formele definitie te staan. In het bijzonder hoeven dus niet alle woorden die erin gebruikt worden formeel gedefinieerd te worden. Formeel is wat in de berekenbaarheidstheorie een "beslissingsprobleem" (of simpel "probleem") genoemd wordt niets anders dan een verzameling ("de verzameling invoerwaarden waarop het antwoord ja is") ofwel de karakteristieke functie van die verzameling (een vraag die met 'ja' of 'nee' beanwoord kan worden). Als je definieert "P(buurman links) = 1" en "P(buurman rechts) = 0", dan heb je een (vrij triviaal) beslissingsprobleem gedefinieerd, ja.

Als je denkt dat je het beter kan, dan graag. Wat je niet moet doen is schrijven dat beslissingsproblemen meer dan twee antwoorden kunnen hebben, of zelfs maar willekeurige antwoorden (je kan die antwoorden in principe noemen zoals je wilt, maar de ene betekent "ja" en de andere "nee"). Wat je ook niet moet doen is schrijven dat beslissingsproblemen altijd beslisbaar moeten zijn. Want dan maak ik daar inderdaad bezwaar tegen. Hoopje (overleg) 11 aug 2022 17:21 (CEST)

Je suggereert allemaal zaken die je niet uit mijn opmerkingen kunt destilleren. En je gaat compleet voorbij aan waar mijn opmerkingen wel over gaan. Daarom:

1.is de vraag: "is mijn buurman gay?" een beslissingsprobleem?

2.Wat is het computationele karakter van een onbeslisbaar beslissingsprobleem?

En verder vind ik het nietszeggend om te stellen dat een beslissingsprobleem een verzameling invoerwaarden is waarop het antwoord ja is. En ook daar. vraag ik me af wat het computationele is. Madyno (overleg) 11 aug 2022 18:33 (CEST)

Nogmaals, ik heb het artikel niet geschreven. Ik heb niet het idee dat de schrijver (die je in de geschiedenis vast kunt achterhalen) de eerste zin als formele definitie heeft bedoeld, en in het bijzonder ook niet over het begrip "computationeel probleem" heeft nagedacht. Mijn bijdragen aan het artikel beperken zich tot het terugdraaien van een paar bewerkingen die uit een informeel artikel een fout artikel maakten en een paar linkfixes. Ik dacht dat jouw vragen bedoeld waren om meer begrip over het onderwerp te krijgen, misschien omdat je het artikel wilde verbeteren, dus wilde ik een beetje achtergrond verschaffen. Maar dan "suggereer ik allemaal zaken die ik niet uit jouw opmerkingen kan destilleren". Soit.

Wat betreft jouw vraag 1: Nee, "is mijn buurman gay" is geen beslissingsprobleem (of hoogstens een zeer triviaal randgeval), want het heeft geen invoer, en het koppelt de invoer niet aan de uitvoer. "Bepaal of een gegeven persoon gay is" zou je als beslissingsprobleem kunnen opvatten als je het predicaat "is gay" duidelijk genoeg vindt. Maar goed, dan begeef je je op hetzelfde niveau waarin verzamelingen madeliefjes ook wiskundige verzamelingen zijn. Ik vind dat nooit zo nuttig.

En je kunt het nietszeggend vinden om een beslissingsprobleem als een verzameling invoerwaarden te defineren, maar in de praktijk komt dat zeker voor. Ik heb hierboven al geprobeerd uit te leggen waarom dat zo is en ik zou er ook over kunnen uitweiden, maar dan loop ik het risico nog meer dingen te suggereren die ik niet uit jouw opmerkingen kan destilleren. Hoopje (overleg) 12 aug 2022 09:53 (CEST)

Ik wil je niks verwijten, Hoopje. Ik hoop het artikel te kunnen verbeteren en beschouw jou als meer deskundig dan mezelf. Vandaar mijn vragerij. Sorry, als je je aangevallem voelt, maar je kunt toch wel tegen een stootje, Want het voorbeeld van mijn buurman wil maar niet landen. In het artikel staat: "Het probleem "is het getal n een priemgetal?" is bijvoorbeeld een beslissingsprobleem, want het antwoord is 'ja' of 'nee', afhankelijk van de invoer, het getal n." Dat lijkt mij niet juist, dwz. de argumentatie, vandaar dat ik mijn buurman ten tonele voerde, En hopelijk kun jij uitleggen wat er computationeel is aan een niet-beslisbaar beslissingsprobleem. Madyno (overleg) 12 aug 2022 10:03 (CEST)

Zoals gezegd weet ik niet wat de oorspronkelijk auteur met "computationeel probleem" bedoeld heeft, maar het is natuurlijk een feit dat men in de berekenbaarheidstheorie ook zeer geinteresseerd is in dingen die niet berekenbaar zijn. Verder begrijp ik nog steeds niet wat je probleem met de (informele) definitie / argumentatie is. Hoopje (overleg) 14 aug 2022 12:20 (CEST)

Hoopje, Je stelt in het voorbeeld van de priemgetallen een te definiëren probleem gelijk aan een verzameling. Madyno en ik vinden dat onduidelijk. ChristiaanPR (overleg) 15 aug 2022 01:16 (CEST)

Ik stel helemaal niks. Ik heb aan het artikel inhoudelijk nauwelijks bijgedragen. Verder vind ik het vrij onbelangrijk wat jullie duidelijk vinden en wat niet. Beslissingsproblemen worden in de praktijk vaak zo gedefinieerd, dat is wat ik belangrijker vind. En ten slotte begrijp ik ook niet wat er onduidelijk aan is. Je weet vast dat elke verzameling een karakteristieke functie heeft. Nu, andersom is dat ook het geval. Hoopje (overleg) 15 aug 2022 07:29 (CEST)

Alleen de indicatorfunctie is op de Nederlandse wikipedia gedefinieerd. ChristiaanPR (overleg) 15 aug 2022 19:22 (CEST)

Whatever, man. Hoopje (overleg) 15 aug 2022 20:44 (CEST)

n'importe quoi ChristiaanPR (overleg) 15 aug 2022 21:06 (CEST)

Het is in de wetenschap nodig gegeven een probleem te kunnen aangeven dat het een beslissingsprobleem is of niet. Een vraag waar het antwoord alleen bevestigend of ontkennend kan zijn heet nu eenmaal een beslissingsprobleem. Het is daarentegen duidelijk overbodig om bij de definitie van weer een ander begrip het begrip beslissingsprobleem in te voeren. Het is dus alleen nuttig om voorbeelden van beslissingsproblemen te geven, maar het is niet nuttig om begrippen als de positieve antwoordverzameling op een beslissingsprobleem te definiëren. ChristiaanPR (overleg) 15 aug 2022 22:09 (CEST)

De positieve antwoordverzameling definieert de vraag. De vraag is namelijk per gegeven input of die daarin zit. - Patrick (overleg) 16 aug 2022 10:05 (CEST)

Nog eens

Is de vraag "Hou je van oesters?" een (computationeel) beslissingsprobleem? Mij lijkt dat onzin, maar volgens het artikel is dat wel zo. Madyno (overleg) 16 aug 2022 23:27 (CEST)

Ik moet zeggen dat ik jouw probleem hiermee nog steeds niet begrijp. Verzamelingen zijn extensioneel, niet intensioneel. Dat betekent dat het, voor verzamelingengelijkheid, alleen maar belangrijk is welke elementen erin zitten, niet vanwege welke voorwaarde ze erin zitten. Dat geldt dus ook voor functies. Het is alleen belangrijk welke uitvoer de voor welke argumenten leveren, niet waarom ze die uitvoer leveren. "Hou je van oesters" (weer zo'n triviaal randgeval zonder invoer, trouwens) is dus ofwel de constante "ja"-functie als "je" van oesters houdt ofwel de constante "nee"-functie als dat niet het geval is. Welke van de twee het is weet ik niet zolang ik niet weet of "je" van oesters houdt. Kortom, jouw probleem is dat je het beslissingsprobleem in vage bewoordingen hebt gedefinieerd, niet een probleem met het begrip "beslissingsprobleem". Hoopje (overleg) 17 aug 2022 07:28 (CEST)

Ik bedoel met 'je' niet speciaal jou, De invoer komt uit een of andere groep personen, zeg V. En dan? Waarin verschilt dit probleem van de vraag: Is n een priemgetal? Madyno (overleg) 17 aug 2022 12:22 (CEST)

Ja en dan? Wat zijn dan de personen die van oesters houden? Het verschil met "is een priemgetal" en "houdt van oesters" is dat "is een priemgetal" precies gedefinieerd is, en "houdt van oesters" niet. Hoopje (overleg) 17 aug 2022 12:26 (CEST)

Dat kan wel zijn, maar net als bij de vraag of n een priemgetal is, moet deze vraag met ja of nee beantwoord worden, en zou dus een computationeel beslissingsprobleem zijn. Alternatief, en dat is wat ik denk, het voorbeeld over priemgetallen klopt niewt. Madyno (overleg) 17 aug 2022 13:30 (CEST)

Je vermoeden is onjuist. "Is een priemgetal" (meestal PRIMES genoemd) is wel een beslissingsprobleem. Het geniet zelfs enige bekendheid wat dat betreft, omdat het lange tijd niet bekend was of het in de complexiteitsklasse P lag. Hoopje (overleg) 17 aug 2022 14:00 (CEST)

Je mist het punt waarom het gaat. Nagaan of n een priemgetal is, is zeker een. beslissingsprobleem, maar de daarvoor gebruikte argumentatie in het artikel is onvoldoende. Daar gaat het mij om! Madyno (overleg) 17 aug 2022 16:47 (CEST)

Ik snap inderdaad niet wat je bedoelt. Ik hou er maar mee op. Hoopje (overleg) 17 aug 2022 16:58 (CEST)

Kom op, Hoopje. In het artikel staat: "Het probleem "is het getal n een priemgetal?" is bijvoorbeeld een beslissingsprobleem, want het antwoord is 'ja' of 'nee', afhankelijk van de invoer, het getal ." Vervang "is het getal n een priemgetal" door "Is je buurman gay?", en wat krijg je: "Het probleem "Is je buurman gay?" is bijvoorbeeld een beslissingsprobleem, want het antwoord is 'ja' of 'nee', afhankelijk van de invoer, de persoon in kwestie." Madyno (overleg) 17 aug 2022 17:33 (CEST)

Wat betekent computationeel probleem dan? En wat is de argumentatie dat de vraag an sich: "is het getal n een priemgetal" een beslissingsprobleem is? Madyno (overleg) 19 aug 2022 00:03 (CEST)

Encyclopedia Britanica: decision problem, for a class of questions in mathematics and formal logic, the problem of finding, after choosing any question of the class, an algorithm or repetitive procedure that will yield a definite answer, “yes” or “no,” to that question. The method consists of performing successively a finite number of steps determined by preassigned rules. In particular, the term is used for such procedures for finding whether—in a particular logistic system, logical calculus, or formal mathematical system—some given “well-formed formula” (generated in accordance with established formation rules) is or is not provable as a theorem of the system.Madyno (overleg) 19 aug 2022 00:09 (CEST)

Encyclopedia of Mathematics: Decision problem (algorithmic problem): The question of the existence of an effective computational procedure or algorithm for deciding the truth of falsity of any instance of a parametric statement. Simple examples of decision problems are: addition of two given decimal numbers, multiplication of two given numbers, the verification of whether or not a given integer is prime, to find the derivative of a given function, to expand a given function into a power series, etc. Madyno (overleg) 19 aug 2022 00:19 (CEST)

Tja, ik kan niet anders zeggen, dan dat die twee bronnen het helaas fout hebben. Ook interessant is overigens dat die "Encyclopedia of Mathematics" lijkt te beweren dat "addition of two given numbers" een "question of the existence of an effective computational procedure or algorithm for deciding the truth of falsity of any instance of a parametric statement" is. 3 + 3 = waar, ofzoziets. Ook de voorbeelden in Brittannica kloppen niet met hun eigen definitie, omdat het zoeken naar dat algoritme niet meer in de voorbeelden voorkomt, maar in ieder geval gebruiken ze daar ja/nee-voorbeelden.

Waarom geloof je die twee bronnen wel, en niet al die literatuur die in ons artikel en het Engelse artikel verlinkt zijn? Bij sommige daarvan kan je de definitie van "beslissingsprobleem" zelfs online bekijken, bijv. hier, of hier (waar overigens ook 'computational problem' gedefinieerd wordt). Hoopje (overleg) 19 aug 2022 07:36 (CEST)

Ik lees dat voorbeeld zo: "is er een algoritme om de som van twee getallen te bepalen." Overigens vind ik niets computationeels aan de zin: "is n een priemgetal?" En dan, als je 2e bron een voorbeeld geeft: "An example of decision problem is the 3-coloring problem: given an undirected graph, determine whether there is a way to assign a “color” chosen from {1, 2, 3} to each vertex in such a way that no two adjacent vertices have the same color." Madyno (overleg) 19 aug 2022 10:12 (CEST)

Aha, ik geloof dat de Encyclopedia Brittanica spreekt over wat hier (evenals op de Engelstalige WP) onvertaald Entscheidungsproblem heet. Dat is een vergelijkbaar begrip uit de logica, maar het is natuurlijk wel ouder dan het modernere begrip beslissingsprobleem zoals dat in de berekenbaarheids- en complexiteitstheorie wordt gebruikt. Hoopje (overleg) 19 aug 2022 10:22 (CEST)

┌────────────────────────────────────────────────────────────────────────────────────────────────────┘Okay, dat moet dan missschien duidelijk gemaakt worden. En nu even over de bron uit Stanford, die is tamelijk onduidelijk in het begin, maar het beschrijft (boldface van mij): "That is, in a decision problem we are only asked to verify whether the input satisfies a certain property." En het voorbeeld zegt: " determine whether there is a way", en dat lijkt me logisch. Wel moet nog duidelijk gemaakt worden welke "ways" dat mogen zijn. Madyno (overleg) 19 aug 2022 10:37 (CEST)

Deze bron zegt: A decision problem is the problem of determining an answer to a class of yes/no questions about some objects of interest.

Ook hier: determining Madyno (overleg) 20 aug 2022 21:00 (CEST)

En hier wordt ook in de complexiteitstheorie gesproken over een 'Entscheidungsproblem' dat wij 'beslissingsprobleem' noemen. Madyno (overleg) 21 aug 2022 00:33 (CEST)

Welk punt probeer je eigenlijk te maken? Wat denk jij dan dat een beslissingsprobleem wel is? Wat is je bedoeling met al die bronnen die een beslissingsprobleem weer in iets andere bewoordingen beschrijven? Ik heb het idee dat je probeert aan te tonen dat ik ongelijk heb, maar zelfs daar ben ik niet zeker van.

Wat jou eerste bron betreft, die tekst die je citeert staat onder het kopje "decision problems as languages" (nadruk van mij) en geeft als voorbeelden van decision problems precies het soort ja/nee vragen waar jij je blijkbaar zo aan stoort. Wat jouw tweede (Duitse) bron betreft, daar wordt op blz. 32. een "entscheidungsproblem" een deelverzameling van de verzameling {0,1}* genoemd, precies zo als ook in ons artikel staat.

Of vind je het vervelend dat ze in Duitsland een "beslissingsprobleem" een "Entscheidungsproblem" noemen? Nou ja, beslissen = entscheiden en probleem = Problem. Dat is natuurlijk ook de reden dat wat wij (en de Engelse Wikipedia) "Entscheidungsproblem" noemen in de Encyclopedia Brittannia als "decision problem" wordt vertaald. Hoopje (overleg) 21 aug 2022 09:18 (CEST)

Goeiemorgen Hoopje, ik hoop alleen maar het artikel te verbeteren, en dat is volgens mij hard nodig. 1. Jij wilde duidelijk maken dat 'Entscheidungsproblem' ook in het Engels en Nederlands een sprecifieke betekenis heeft. En dat klopt. Maar ik laat zien dat het daarnaast ook de betekenis van 'beslissingsprobleem heeft, zoals in dit artikel aan de orde is. 2. Ik vind de omschrijving in de intro onvoldoende. Volgens mij - en daar helpt de logica - is niet de ja/nee-vraag het beslissingsprobleem, maar de vraag of er een algoritme is om de vraag te beantwoorden. En daarin wordt ik door de genoemde bronnen gesteund. Bovendien denk ik dat de bronnen die een ja/nee-vraag als beslissingsprobleem noemen, wel degelijk de berekenbaarheid, dus een algoritme, in hun achterhoofd hebben. 3. De priemgetallen. De aanvankelijk argumentatie in de intro bij het voorbeeld van de priemgetallen was onvoldoende. Nu heb jij die weggehaald en staat er alleen maar dat het een voorbeeld is. Maar ik vind dat genoemd moet worden waarom dat voorbeeld een voorbeeld van een beslissingsprobleem is. En ik denk dat dan vanzelf de vraag naar een algoritme opdoemt. Het beslissingsprobleem is: "Is er een algoritme om uit te maken of een getal n een priemgetal is?" of "Kan een algoritme beslissen of een getal n een priemgetal is?" 4. Dan wil ik nog erover discussiëren wat het betekent dat het priemgetalvoorbeeld gemodelleerd zou kunnen worden door de natuurlijke getallen en de deelverzameling PRIMES. Wat zegt PRIMES meer dan dat de elementen de priemgetallen zijn? En daar heb ik PRIMES toch niet voor nodig? 5. Ik geef je een lijstje met chemische stoffen en vraag voor elke stof: is deze stof een zuur? Is dit een beslissingsprobleem? Madyno (overleg) 21 aug 2022 09:59 (CEST)

1. In het Duits heeft "Entscheidungsproblem" inderdaad (ook) de betekenis "beslissingsprobleem". Maar in het Nederlands of het Engels betekent "Entscheidungsproblem" nooit de soort beslissingsprobleem die in dit artikel besproken wordt. Het is namelijk een Duits woord. "Decision problem" betekent blijkbaar soms ook "Entscheidungsproblem". Of dat ook geldt voor "beslissingsprobleem", weet ik niet, maar in ieder geval heb ik daarom ook al een "Zie ook" opgenomen.

2-4. Nogmaals, nee. Het zoeken naar een algoritme is niet deel van het beslissingsprobleem. En je wordt ook niet door andere bronnen gesteund, want in de bronnen die jij zelf opnoemt (en die ik zelf kan inzien) wordt een beslissingsprobleem overal een taal of een deelverzameling van {0,1}* genoemd. Precies wat nu al in het artikel staat. Het beslissingsprobleem is de specificatie waarin het gezochte algoritme moet voldoen. Het is de vraag die het algoritme moet oplossen. Soms bestaat dat algoritme (PRIMES), soms bestaat het niet (stopprobleem). Soms zijn we ook niet in een willekeurig algoritme geinteresseerd, maar in een die aan bepaalde extra eisen voldoet (wat betreft looptijd, bijvoorbeeld). Het zou dus ook heel lastig zijn als het zoeken naar het algoritme deel van het probleem zou zijn, want dan zou de gezochte soort algoritme ook deel van het probleem zijn en dan zouden we niet kunnen zeggen: PRIMES is in P (lees ook de eerste zin van de tweede alinea van de inleiding).

5. Wat denk je nou met dat soort voorbeelden te bereiken? Is het feit dat ik jou om je oren kan zeuren over of een bepaalde stof een element is van "de verzameling zuren" een aanwijzing dat het begrip "verzameling" fout is? Nee, het is een aanwijzing ervoor dat het voorbeeld niet deugt. Maar laat ik de proef op de som nemen. Laat X de verzameling zuren zijn. Zo Madyno, beantwoord dan maar eens, met zuiver wiskundige argumenten, de vraag: is "zure regen" element van X? Hoopje (overleg) 21 aug 2022 11:35 (CEST)

Eerst maar punt 5. Er is niks mis met het voorbeeld van de stoffen. Ik precisieer het: je krijgt een lijst (verzameling) met 100 chemische stoffen. Vraag: Is stof nr. N een zuur? Als je vindt dat dit voorbeeld essentieel verschilt van PRIMES, dan hoor ik graag waar dat verschil in zit. Anders is het ook een beslissingsprobleem. Madyno (overleg) 21 aug 2022 19:41 (CEST)

PRIMES is niet een lijst getallen, het is een lijst priemgetallen. Je moet me geen lijst stoffen geven, maar een lijst zuren. Een oneindige lijst, eventueel, of iets anders dat precies beschrijft wat een zuur is. Kortom, er is wel degelijk een hoop mis met jouw voorbeeld. (Jouw lijstje van 100 stoffen is natuurlijk ook een beslissingsprobleem, maar dan een die overeenkomt met de vraag "staat stof x op Madyno's lijstje?") Hoopje (overleg) 21 aug 2022 20:42 (CEST)

Wil je het niet zien? Ik geef je $\mathbb {N}$ en vraag: Is $n\in \mathbb {N}$ een priemgetal? Daarbij ga ik ervan uit dat 'priemgetal' al gedefinieerd is. Volgens mij is dit het voorbeeld uit het artikel. Nu geef ik je $L$ een verzameling chemische stoffen en vraag: is stof $n\in L$ een zuur? Daarbij ga ik ervan uit dat 'zuur' al gedefinieerd is. Kan ik het nog duidelijker stellen? Wat is het verschil? Madyno (overleg) 21 aug 2022 21:33 (CEST)

Als "zuur" zo precies gedefinieerd is volgens jou, is "zure regen" dan een zuur of niet? Hou toch op met die vage onzin en ga wiskunde doen. Hoopje (overleg) 21 aug 2022 22:43 (CEST)

Zure regen is geen zuur. Nu jij, wat is het verschil tussen mijn twee vootbeelden. Madyno (overleg) 22 aug 2022 16:12 (CEST)

En waarom is zure regen geen zuur? Wat betekent "zuur" dan precies? Ik neem aan dat de invoer een structuurformule is, maar zelfs dat moet ik raden. Ik weet wat een priemgetal is, en dus weet ik welke elementen PRIMES heeft. Ik weet niet wat jij met "zuur" bedoelt, en dus weet ik niet wat de elementen van de verzameling ZUREN zijn. Hou toch liever op met die vage onzin en ga wiskunde doen. Hoopje (overleg) 22 aug 2022 16:26 (CEST)

Weet je wat een steenvrucht is? Madyno (overleg) 23 aug 2022 11:42 (CEST)

Als je nog van plan was een punt te maken met dat vage gedoe, kan je dat beter direct doen in plaats van dit soort vervelende spelletjes te spelen. Totdat je dat punt gemaakt hebt was dit mijn laatste bijdrage aan deze "discussie". Hoopje (overleg) 23 aug 2022 12:13 (CEST)

Mijn punt heb ik al tig keer gemaakt, maar je wil het niet zien. Daarom zulke vervelende (?) spelletjes. Het gaat mij om jouw medewerking. De vraag: "is n een priemgetal?" is kennelijk een beslissingsprobleem. Daarom stel ik een andere vraag: "is deze vrucht een steenvrucht?" Of een andere volgens jou vervelende vraag. En logischerwijze (wiskunde) is dan de vervolgvraag: "is dit een beslissingsprobleem?" Ik denk van. niiet, maar ik zie geen verschil met de vraag naar een priemgetal. En dus ontbreekt er iets in het artikel. Madyno (overleg) 23 aug 2022 13:58 (CEST)

Nou goed. Ik doe maar net alsof dat een "punt" is dat je gemaakt hebt en geen stompe paal, en reageer nog maar een keer.

De enige reden dat jij denkt dat "is deze vrucht een steenvrucht" geen beslissingsprobleem is, is omdat het een vaag voorbeeld is. Zoals je in het artikel kunt lezen (onder Definitie) is een beslissingsprobleem een deelverzameling van de verzameling mogelijke invoerwaarden (waar formeel de mogelijke invoerwaarden ook nog rijtjes symbolen zijn, maar dat wordt vaak impliciet gelaten). "Verzameling" is een wiskundig begrip. "Vrucht", "Steenvrucht", "Zuur" en "Buurman" zijn dat niet. Stel er liggen drie appels in mijn fruitschaal. Hoeveel elementen heeft de verzameling vruchten in mijn fruitschaal? Ik weet dat {1,1}={1}, dus geldt ook {appel, appel, appel} = {appel}? Of is het meer {appel1, appel2, appel3} ? En als ik je nu vertel dat een appel een Granny Smith en de andere twee Jonagolds zijn, is die verzameling dan {GrannySmith, Jonagold}? Het heeft toch geen zin daarover te praten? Vage onzin is dat. En als je als "tegenvoorbeeld" alleen met vage onzin op de proppen kunt komen, dan vind ik dat inderdaad wat treurig, vooral als je dan ook nog meent je "punt" met een flauw vraag-en-antwoord-spelletje over te moeten brengen.

Een verzameling steenvruchten en een verzameling zuren bestaan niet. In ieder geval niet totdat je de begrippen "vrucht", "steenvrucht", "stof" en "zuur" zover geformaliseerd hebt dat het in feite wiskundige objecten zijn geworden. En op dat moment is het niet meer zo tegenintuitief om het als een beslissingsprobleem op te vatten. Ik heb geen idee hoe jij denkt vruchten en buurmannen te formaliseren. Maar laat ik eens op jouw zuren ingaan. Die zou je als een structuurformule kunnen formaliseren. En dan kun je vragen "is 'H20' een zuur?" (nee) of "is 'HNO3' een zuur" (ja). Dan ziet het er intuitief plotseling al veel meer als een beslissingprobleem uit (gegeven door de verzameling structuurformules van zuren). Sterker nog, ik kan me voorstellen dat het een beslisbaar beslissingsprobleem is (maar ik ben geen chemicus).

En ten slotte wil ik nog even opmerken dat jouw door mij teruggedraaide verbetering van 18 augustus de zin `Het probleem "is er een algoritme dat bepaalt of het getal $n$ een priemgetal is?" is bijvoorbeeld een beslissingsprobleem' bevatte. Jouw eigen formulering is (behalve dat hij ook nog eens niet klopte) net zo weinig bestand tegen vage onzin als de zin die jij schijnbaar wilt veranderen. Is "is er een algoritme dat bepaalt of een vrucht een steenvrucht is?" een beslissingsprobleem? Hoopje (overleg) 23 aug 2022 15:38 (CEST)

Toevoeging: Zo, en verder ga ik niks meer over zulke vage onzin zeggen. Er valt vast veel aan het artikel te verbeteren. Als je voorstellen tot verbetering hebt, ik ben benieuwd. Maar hou op met die vage onzin en ga wiskunde doen. Hoopje (overleg) 23 aug 2022 15:42 (CEST)

Goed dat je nog eens reageerde. Met mijn vage onzin wilde ik alleen maar de vraag opwerpen of elke ja/nee-vraag wel een beslissingsprobleem is. Mogelijk kun je veel kriteiek op mijn voorbeelden hebben, maar essentieel is het voorgaande. En dan liet ik zien dat er bronnen zijn die zeggen dat niet de vraag zelf, maar de vraag naar een algoritme dat de vraag beantwoord een beslissingsprobleem is. Dat lijkt mij ook logischer en komt tegemoet aan het computationele karakter. Ik ben maar een leek op dit gebied, maar zie wel of iets logisch is of niet. Zo lijkt het me volslagen zinloos de vraag of een getal een priemgetal is te vervangen door de verzameling priemgetallen. Wat helpt dat als ik vraag of 123567891111131415117 een priemgetal is? Madyno (overleg) 23 aug 2022 16:55 (CEST)

Jouw bewering dat je bronnen had gevonden die zeggen dat de vraag naar een algoritme het beslissingsprobleem is, heb ik al weerlegd in mijn bijdrage van 21 augustus, 11:35 uur. In die bijdrage heb ik ook aangetoond dat het nu juist niet zo logisch is om een beslissingsprobleem als "de vraag naar een algoritme" te definieren, en zelfs een wetenschappelijk artikel verlinkt waar PRIMES als de verzameling priemgetallen wordt gedefinieerd. Je koos er toen echter voor alleen op punt 5, de vage onzin, in te gaan. De rest ga ik nu niet herhalen. Je zou kunnen zeggen dat men op zoek is naar algoritmes om bepaalde ja/nee-problemen op te lossen. Het is nu eenmaal zo dat die op te lossen ja/nee-problemen "beslissingsproblemen" heten, en dat zoeken naar een algoritme niet (en dat zoeken naar een algoritme met polynomiale looptijd ook niet, en dat zoeken naar een niet-deterministisch algoritme met polynomiale looptijd ook niet, en dat zoeken naar een eindige automaat ook niet, etc, etc, etc). Hoopje (overleg) 23 aug 2022 20:14 (CEST)

Discussie

@ChristiaanPR, Patrick: Ik vind veel onduidelijk in het artikel en wil stapsgewijs verbeteringen aanbrengen. Hopelijk willen juliie ook meedenken.

1. De omschrijving in de intro van een beslissingsproces is volgens mij niet correct. Ik heb geprobeerd dat aan Hoopje voor te leggen, maar zonder resultaat. Als namelijk de omschrijving correct zou zijn, zou volgens mij ook de vraag: "Is je buurman gay?" een beslissingsprobleem zijn. Commentaar? Madyno (overleg) 24 aug 2022 11:44 (CEST)

Madyno, Jouw voorbeeld is geen voorbeeld uit de berekenbaarheids- of complexiteitstheorie. Die voorwaarde wordt in de eerste zin van het artikel gesteld. Ik begrijp ook niet zo goed waarom je steeds op dat voorbeeld blijft hameren. ChristiaanPR (overleg) 24 aug 2022 17:15 (CEST)

Wanneer komt een probleem uit de berekenbaarheids- of complexiteitstheorie? Of beter, wat is een computationeel probleem? Ik schreef: "Computationeel houdt daarbij in dat de oplossing in de vorm van een algoritme moet worden gevonden.", maar dat werd verwijderd door Hoopje. Madyno (overleg) 24 aug 2022 18:46 (CEST)

De inleiding is nu redelijk duidelijk, maar moet om 'zelfomvattendheid' te bereiken nog specifieker:

• Het gaat om het probleem om van elk element van een gegeven verzameling te kunnen bepalen of het een gegeven eigenschap heeft.
• Gegeven die verzameling wordt een beslissingsprobleem dus gegeven door de te bepalen eigenschap.
• Het is standaardpraktijk om die eigenschap te definiëren als de deelverzameling van de elementen met de gevraagde eigenschap. (Dit is m.i. incorrect, omdat het onbeslisbaar kan zijn of voor twee gegeven eigenschappen precies dezelfde objecten er aan voldoen; maar het is nu eenmaal gebruikelijk.)
• Het gaat om wiskundige eigenschappen van wiskundig gedefinieerde objecten. (Buurman en gay zijn geen wiskundige begrippen, maar betreffende een wiskundig model dat beschrijft waar mensen wonen en wat hun seksuele voorkeuren zijn, kan de vraag of een buurman gay is een beslissingsprobleem zijn.)
• Elk object moet eindig representeerbaar zijn. Dit komt denk ik op hetzelfde neer als zeggen dat de verzameling aftelbaar moet zijn. (Een eigenschap van reële getallen bepalen is dus geen beslissingsprobleem.)
• In de praktijk worden eigenlijk altijd beslissingsproblemen beschouwd over de verzameling natuurlijke getallen of de verzameling eindige tekenreeksen over een gegeven eindig alfabet.
• De wiskundige definitie van de eigenschap is in de praktijk denk ik altijd te geven als een formule in de predicatenlogica. Er lijkt me in elk geval een nadere specificatie nodig. Maar misschien niet in de inleiding.

Rp (overleg) 25 aug 2022 20:50 (CEST)

• Zoals je al zegt, gat het om het kunnen bepalen of het element de gevraagde eigenschap heeft. En daar moet volgens mij aan toegevoegd worden: computationeel bepalen, dus door middel van een algoritme (in ruime zin).
• De gevraagde eigenschap bepaalt het probleem, dat is juist, maar het probleem is niet alleen de beantwoording van de vraag of het element de eigenschap heeft.
• De deelverzameling van de elementen met de gevraagde eigenschap zegt niets meer dan de eigenschap.
• Zoals ik in een eerdere versie deed, verklaren wat computationeel betekent.
• Als de verzameling invoerelemeten eindig is, kan moeiteloos voor elk element beslist worden. Ik kan nog niet zien waarom die niet overaftelbaar zou mogen zijn. De vraag of een reeel getal geheel is, lijkt mij een goed beslissingsprobleem.

Madyno (overleg) 25 aug 2022 23:58 (CEST)

• Ik vind 'computationeel' te vaag. Het is beter zom dit specifiek te maken. Vandaar dat ik schrijf dat elk element van de mogelijke invoer eindig representeerbaar moet zijn.
• Niet eisen dat een algoritme de eigenschap kan beslissen: een beslissingsprobleem hoeft niet beslisbaar te zijn.
• Het probleem is wel degelijk om van een willekeurige invoerelement te bepalen of het de gevraagde eigenschap heeft, dwz. tot de gedefinieerde verzameling behoort. Het probleem is niet om te bepalen of er een algoritme bestaat die dat doet: dat is het probleem van de beslisbaarheid van een beslissingsprobleem.
• Hoe wil je elk element van een overaftelbare verzameling als invoer aan een algoritme aanbieden? Het niet kunnen aanbieden van elk invoerelement mag geen hinderpaal zijn.

Rp (overleg) 1 sep 2022 01:06 (CEST)

1. Als computationeel te vaag is, moet de intro gewijzigd worden.
2. Dat er een algoritme bestaat, is volgens mij niet hetzelfde als beslisbaar. Dat staat wel hier en daar, maar de Engelse W. geeft aan dat beslisbaar betekent dat een algoritme in eindige tijd de vraag moet kunnen beantwoorden.
3. Dan wordt het mogelijk dat de vraag op een andere manier dan met een algoritme, beantwoord wordt.
4. Hoe zit dat met aftelbaar oneidndig?

Madyno (overleg) 1 sep 2022 09:35 (CEST)

1. Waarom moet de introductie volgens jou altijd meteen een volledig formele definitie zijn? Dat is me bij andere lemma's ook wel eens opgevallen. De introductie is, in ieder geval hier, informeel. Daar mogen "vage" woorden in voorkomen. Onder het kopje "Definitie" staat een formele definitie. Sterker nog, er staan twee (equivalente) formele definities. Daarin komt het wordt computationeel niet meer voor. Maar goed, van mij mag je het woord "computationeel" weghalen hoor, als je daar blij van wordt.
2. Een algoritme dat oneindig doorloopt levert geen uitvoer. Dat loopt oneindig door. De Engelse Wikipedia kiest er blijkbaar voor dat "in eindige tijd" er nog maar expliciet bij te zetten, maar nodig is dat niet.
3. Ja? En?
4. Zoals je onder het kopje "Definitie" kunt lezen, zijn de mogelijke invoerwaarden strings over een eindig alfabet. Dat is een aftelbaar oneindige verzameling. Rp noemde hierboven ook nog, dat soms ook natuurlijke getallen als invoerwaarden worden genomen (die zijn voor complexiteitstheorie echter wat minder geschikt, omdat de "grootte" niet overeenkomt met de waarde). De natuurlijke getallen zijn ook een aftelbaar oneindige verzameling. En dat PRIMES, eveneens een aftelbaar oneindige verzameling, een beslissingsprobleem is, hadden we al vastgesteld. Dus wat is precies je vraag?

Hoopje (overleg) 1 sep 2022 18:44 (CEST)

1. In de intro introduceer en verduidelijk ik het begrip op informele wijze. Maar als de intro niet volledig is, moet dat wel duidelijk zijn. En er moet natuurlijk geen onzin in staan of begrippen die eerder vragen oproepen, dan antwoorden geven.
2. Kan een iteratieve procedure voor sommige invoer niet-aflopend zijn? En is het dan geen algoritme?
3. Dan zijn al die "vage' voorbeelden toch beslissingsproblemen?
4. Ja, want geef mij een natuurlijk getal, en ik heb een algoritme dat uitmaakt of het priem is. Dat kan voor elk natuurlijk getal, maar niet voor alle. Geef mij een reêel getal en ik heb een algoritme dat uit

Madyno (overleg) 2 sep 2022 08:42 (CEST)

1. Waarom zou de huidige introductie niet volledig zijn? Het is een informele inleiding, dan hoeven niet alle details ingevuld te worden.
2. Natuurlijk kan een "iteratieve procedure" voor sommige invoer niet termineren. Maar dan is dat geen beslissingsprocedure, want die moet voor alle mogelijke invoer het juiste antwoord geven en niet af en toe geen antwoord geven.
3. Ik val in herhaling: dat zijn op een zeer hoog informeel niveau beslissingsproblemen. Op een nog hoger informeel niveau dan de huidige inleiding. Op hetzelfde niveau is een verzameling madeliefjes ook een verzameling. Het is gewoon niet nuttig daar de hele tijd over te beginnen, want het biedt geen enkel inzicht. Dus hou op met die vage onzin en ga wiskunde doen.
4. Het kan voor elk natuurlijk getal, inderdaad. Maar een algoritme kan niet elk reeel getal als invoer nemen, want niet elk reeel getal is als een eindig rijtje symbolen te representeren.
5. Ik geloof niet (meer) dat jij als zelfverklaarde leek op dit gebied zinvol aan de verbetering van dit artikel gaat bijdragen. Ga je dus liever op iets anders richten.

Hoopje (overleg) 2 sep 2022 13:17 (CEST)

Ik denk dat ik wel degelijk aan de hoognodige verbetering kan bijdragen. Stap voor stap. De inleiding spreekt van een "computationeel" probleem. Dat roept eerder vragen op dan dat het iets verduidelijkt. Ik stel voor de term "computationeel" uit te leggen. Madyno (overleg) 12 sep 2022 12:26 (CEST)