last van onoplosbare algoritmische problemen?

[Bananenplant]

(ik heb dit maar in W&L gedaan, maar misschien had het in een tech-forum gemoeten).

ik heb bij m'n studie nu wat onoplosbare problemen gezien (Haltingprobleem bijvoorbeeld), en ik vraag me nu af: hoeveel last heb je daarvan? zijn er voorbeelden van programma's die men wou schrijven en die vervolgens stuitten op het feit dat het niet algoritmisch aan te pakken is?

[Verwijderd]

ik heb er geen problemen mee, niets is onoplosbaar, ik kan alles oplossen!!!! (met oploskoffie)

[Rey Nemaattori]

bijna elk programma is algoritmisch uit te schrijven, anders plak je er gewoon een andere subroutine tussenin die je terug "loopt" naar het hoofdprogramma... toch???

[Lord Daemon]

Wat bedoel je precies? Heb je het over stelsels vergelijkingen die niet analytisch oplosbaar zijn? (Zoals 3 of meer lichamen die om elkaar heen bewegen dmv van de zwaartekracht - of eigenlijk bijna ieder ander fysisch systeem ) Daar heb je heel veel last van, de halve natuurkunde bestaat uit benaderingsmethoden enzo om toch nog iets te kunnen zeggen, heb ik wel eens het gevoel.

[FCA]

algoritmes? Zou ik niet weten.
Onbewijsbare stellingen zijn in de wiskunde wel degelijk een probleem. Continuum-hypothese van Cantor bijvoorbeeld. Bewezen is dat ie niet op te lossen valt, terwijl het een behoorlijk fundamentele stelling is.

Binnen de natuurkunde ook, zoals LD al opmerkte. Hoewel daar voor het echte rekenwerk veel benaderingen kunnen, en mogen worden gebruikt, aangezien je toch nooit alles exact kunt bepalen.

Over algoritmes: Misschien kun je van bepaalde programma's niet bewijzen dat ze consistent zijn ofzo. Ik zou het niet weten (doe geen informatica), maar misschien zou je zoiets kunnen gebruiken om te bewijzen dat er geen perfecte virusscanner bestaat ofzo, die ook alle onbekende virussen kan pakken.

[Confusion]

Zie hier over het Halting problem:
http://www.cs.washington.edu/homes/csk/halt.html

Dit soort onoplosbare problemen bedoelt de topicstarter denk ik. Dus niet onopgeloste wiskundige problemen en niet zeer moeilijk te berekenen problemen (NP compleet e.d.).

[FCA]

Die bedoelde ik ook niet Fused...

De welbekende Turing paradox (ook wel Halting probleem), is gewoon een speciaal geval van de stelling van Gödel (goed, ik ken geen bewijzen hiervoor, maar ik denk dat er een verband tussen zit).
Wat hierboven werd genoemd zijn fundamenteel onoplosbare problemen in andere, gerelateerde vakgebieden. Aangezien LD en ik beide niet zoveel verstand van programmeren hebben (tenminste, volgens mij studeert LD geen informatica ) geven wij beiden voorbeelden van vergelijkbare problemen uit deze vakgebieden, en hoe deze veel invloed hebben op deze vakgebieden. Daaruit zou je kunnen extrapoleren (erg gevaarlijk, ik weet het) dat dit probleem ook aan de orde komt in de informatica. Ik denk aan een programma dat checkt of er nog bugs ergens in zitten. Het lijkt mij mogelijk om hiervan de onmogelijkheid te bewijzen analoog aan de Turing paradox.

Excuses als Fused niet mij en LD's replies bedoelde

[GeeBee]

zijn er voorbeelden van programma's die men wou schrijven en die vervolgens stuitten op het feit dat het niet algoritmisch aan te pakken is?

Ik denk dat je met Windows een heel end in de richting komt ..

Maar ff serieus
Ik denk dat je daar met programmeren niet zo snel tegenaan zult lopen, tenzij je daar echt op uit bent.
En programma is namelijk een algoritmische benadering van de werkelijkheid en daarom altijd een versimpeling daarvan. Ik verwacht daarom niet dat je in een versimpeling van de werkelijkheid tegen de fundamentele grenzen van diezelfde werkelijkheid aan zult lopen...

[Confusion]

FCA schreef:
Onbewijsbare stellingen zijn in de wiskunde wel degelijk een probleem. Continuum-hypothese van Cantor bijvoorbeeld. Bewezen is dat ie niet op te lossen valt, terwijl het een behoorlijk fundamentele stelling is.

Ik dacht dat de tweede stelling van Godel zegt dat je van een onbewijsbare hypothese niet kan achterhalen dat het onoplosbaar is.

Even zoals ik het verwoord:
1e stelling: Binnen een set axiomas zijn er hypothesen te formuleren die niet binnen de set te bewijzen zijn

2e stelling: Je kan van een onbewijsbare hypothese niet aantonen of deze binnen de set te bewijzen is.

Zit ik ernaast?

[Confusion]

Lord Daemon schreef:
Wat bedoel je precies? Heb je het over stelsels vergelijkingen die niet analytisch oplosbaar zijn? (Zoals 3 of meer lichamen die om elkaar heen bewegen dmv van de zwaartekracht - of eigenlijk bijna ieder ander fysisch systeem ) Daar heb je heel veel last van, de halve natuurkunde bestaat uit benaderingsmethoden enzo om toch nog iets te kunnen zeggen, heb ik wel eens het gevoel.

Daarentegen kan je wel (meestal) de orde van de fout in de benadering geven ens je kan wel bewijzen dat de benadering juist is. Ik vind numerieke wiskunde een mooi vak

[Bananenplant]

Op woensdag 05 december 2001 00:43 schreef Fused het volgende:
Zie hier over het Halting problem:
http://www.cs.washington.edu/homes/csk/halt.html

Dit soort onoplosbare problemen bedoelt de topicstarter denk ik. Dus niet onopgeloste wiskundige problemen en niet zeer moeilijk te berekenen problemen (NP compleet e.d.).

hij snapt het. problemen waar je geen algoritme bij kunt schrijven.