Archief - Vraagje of dit mogelijk is

Gurdt · 15 nov 2010

Bewijsje dat dat onmogelijk is:

Stel u een Turing-machine voor die bepaalt of een programma stopt of niet.
Als het stopt, loopt deze TM oneindig door, als het niet stopt, stopt deze TM.
Voer nu deze TM op zichzelf uit... ohow, contradictie, pijn in de kop!
Namelijk, deze TM bepaalt op hijzelf stopt, en als da zo is, loopt hij,en andersom, dus deze TM is false.

Gurdt · 15 nov 2010

Sorry, ik bedoel backtracking, wat ook recursief is...
Backtracking lijkt me hier wel vantoepassing...

Even rechtzetten; backtracking is niet noodzakelijk recursief

MilM · 15 nov 2010

@topicstarter:

wat is de bedoeling van stap 2 precies?
"Stap 2: Neem de volgende doos in rij met de laagste density (Gewicht/Volume)"

Ik zou eerder verwachten dat de dozen die meer wegen (bij eenzelfde volume) eerst aan bod komen? (anders kun je op het einde voor het laatste schap overblijven met alle zware dozen en moet je terugkeren om dozen te verwijderen en opnieuw te beginnen)

-) Gelden de gewichtsrestricties enkel op niveau van schappen of zijn er meer restricties zoals dat een doos met een bepaald gewicht maar zoveel kg dozen bovenop hem kan dragen?
-) Mag je een grotere doos bovenop een kleinere plaatsen (groter zoals in dieper of breder)?

Over de programmeerbare discussie:

Het is maar wat je verstaat onder 'programmeerbaar'

Moet er dan een stopconditie zijn voor iets als programmeerbaar beschouwd kan worden?
Een programma die een geldig algoritme implementeert, maar toch in een oneindige lus terecht komt (door het algoritme) lijkt mij toch ook een programma.

Mij lijkt het logisch dat programmeerbaar en beslisbaar niet hetzelfde zijn.

Als ik dan een voorbeeld moet geven van iets dat niet programmeerbaar is, dan zou ik eerder denken aan een echte randomizer dan aan een onbeslisbaar probleem.

voltje · 15 nov 2010

Gurdt zei:
Even rechtzetten; backtracking is niet noodzakelijk recursief

Nee ok maar hoe dat ik zijn "opgave" begrijp komt het over als je verschillende combinaties moet doorzoeken tot je de juiste combinatie hebt gevonden.
Waardoor bij mij dus backtracking opkwam.
Aangezien ik dat al wel gebruikt heb om de perfecte uitkomst te zoeken van bepaalde problemen...
Nuja ik kan er naast zitten he, t was gwn mijn 2 cent ;-)

Gurdt · 15 nov 2010

Over de programmeerbare discussie:

Het is maar wat je verstaat onder 'programmeerbaar'

Moet er dan een stopconditie zijn voor iets als programmeerbaar beschouwd kan worden?
Een programma die een geldig algoritme implementeert, maar toch in een oneindige lus terecht komt (door het algoritme) lijkt mij toch ook een programma.

Mij lijkt het logisch dat programmeerbaar en beslisbaar niet hetzelfde zijn.

Als ik dan een voorbeeld moet geven van iets dat niet programmeerbaar is, dan zou ik eerder denken aan een echte randomizer dan aan een onbeslisbaar probleem.

Net niet he, het haltingprobleem bijvoorbeeld, kunt gij nie in code zetten. Het bewijs van dat haltingprobleem bijvoorbeeld draait er net om dat ge geen Turingmachine kunt schrijven die bepaalt of een meegegeven Turingmachine en bijhorende input (lees: een programma) ooit stoppen of niet. Moest ge aannemen dat dat wel kan, kan je heel gemakkelijk via contradictie bewijzen dat dat niet kan

Niet alle problemen zijn oplosbaar, dus ook niet codeerbaar

Zoals je zegt van je random getallen, dat is een analoog probleem, niet oplosbaar of codeerbaar

MilM · 15 nov 2010

Gurdt zei:
Net niet he, het haltingprobleem bijvoorbeeld, kunt gij nie in code zetten. Het bewijs van dat haltingprobleem bijvoorbeeld draait er net om dat ge geen Turingmachine kunt schrijven die bepaalt of een meegegeven Turingmachine en bijhorende input (lees: een programma) ooit stoppen of niet. Moest ge aannemen dat dat wel kan, kan je heel gemakkelijk via contradictie bewijzen dat dat niet kan

Niet alle problemen zijn oplosbaar, dus ook niet codeerbaar
Zoals je zegt van je random getallen, dat is een analoog probleem, niet oplosbaar of codeerbaar

Ik reageerde eigenlijk niet op u, maar ik begin nu zelf te twijfelen als ik de definitie van onbeslisbaar opzoek.

In praktijk kan je iets echt random doen, maar het is onmogelijk om daarvoor een programma te schrijven die aan alle statische eigenschappen voldoet van een echte randomizer.

De manier om iets te randomizen kan dus niet volledig nagebootsts worden.

Mij is het nu onduidelijk of onbeslisbare problemen slaat algemeen op 'problemen die geen oplossing hebben' of problemen waarvoor een mens wel een oplossing kan vinden maar die onmogelijk door de PC opgelost kunnen worden.

(een mens kan bijvoorbeeld wel controleren of een programma zal stoppen)

Nuja, op zich is de discussie niet relevant, maar als het enkel slaat op de laatste groep, dan heb je wel gelijk dat alle onbeslisbare problemen niet programmeerbaar zijn (aangezien dat dan de definitie is van onbeslisbaar) en was ik fout.

nguaroth · 15 nov 2010

MilM zei:
Ik reageerde eigenlijk niet op u, maar ik begin nu zelf te twijfelen als ik de definitie van onbeslisbaar opzoek.

In praktijk kan je iets echt random doen, maar het is onmogelijk om daarvoor een programma te schrijven die aan alle statische eigenschappen voldoet van een echte randomizer.

De manier om iets te randomizen kan dus niet volledig nagebootsts worden.

Mij is het nu onduidelijk of onbeslisbare problemen slaat algemeen op 'problemen die geen oplossing hebben' of problemen waarvoor een mens wel een oplossing kan vinden maar die onmogelijk door de PC opgelost kunnen worden.

(een mens kan bijvoorbeeld wel controleren of een programma zal stoppen)

Nuja, op zich is de discussie niet relevant, maar als het enkel slaat op de laatste groep, dan heb je wel gelijk dat alle onbeslisbare problemen niet programmeerbaar zijn (aangezien dat dan de definitie is van onbeslisbaar) en was ik fout.

De definitie van beslisbaarheid is gewoon: je kan er een programma(turing machine) voor maken dat altijd stopt op alle input.
Dus onbeslisbaarheid betekent gewoon dat er geen enkel programma bestaat dat dit probleem beslist. Dus er is geen enkel programma dat dit probleem oplost

Albireo · 15 nov 2010

Het is een interessant probleem. Mag je dozen roteren? En moeten de stapels dozen keurig naast mekaar staan of mag je dozen uit naburige stapels in mekaar schuiven alsof het een 3D tretis spel is? Dat zijn 2 mogelijkheden die het aantal mogelijke oplossingen gigantisch doen toenemen.

Hoedanook, ik zou i.p.v. een algoritme proberen te schrijven dat een zo goed mogelijke oplossing geeft een algoritme maken dat gedurende een beperkte tijd willekeurige oplossingen berekent en daaruit de beste kiest. Ik zou wel proberen wat optimalisaties proberen in te bouwen, bv eerst de zwaarste dozen gelijkmatig over alle rekken verdelen.

Cycloon · 15 nov 2010

nguaroth zei:
De definitie van beslisbaarheid is gewoon: je kan er een programma(turing machine) voor maken dat altijd stopt op alle input.
Dus onbeslisbaarheid betekent gewoon dat er geen enkel programma bestaat dat dit probleem beslist. Dus er is geen enkel programma dat dit probleem oplost

Maar ook als je een programma schrijft dat oneindig blijft doorgaan heb je software geschreven die het probleem beschrijft. Dat een stuk software niet zomaar een ander stuk software kan analyseren is een feit, dat is net zoals het probleem dat een mens nooit zal kunnen zien of er vertakkingen zijn in de 4de dimensie. Tenzij je een observator bent van een hoger niveau zal je nooit een probleem kunnen oplossen dat zich stelt in een ander niveau (of je eigen niveau). Maar dat zijn louter theoretische problemen, omdat wij die "problemen" zelf zien, maar ze er in wezen nooit zullen zijn voor de software. Het halting probleem stelt zich wel degelijk op het niveau van een software-niveauprobleem en niet op een mens-niveauprobleem.

Geef mij één praktisch probleem dat zich stelt in het bedrijfsleven dat niet in software zou kunnen uitgedrukt worden. Software schrijven om de uitvoering van een ander stuk software te analyseren zonder specifieke input van dat 2de stuk software te definiëren is iets wat in praktijk nooit zal gevraagd worden. Vermits de TS het heeft over een dergelijk praktisch probleem zal er stééds een stuk software geschreven kunnen worden die zijn probleem kan verwerken. Wie het tegendeel beweerd moet dringend van achter de boeken komen!

Gurdt · 15 nov 2010

Er bestaan thans heel bekende stukken software die zichzelf gebruiken, vele virussen bijvoorbeeld.
Een anti-virusprogramma analyseert op zijn beurt stukken software om structuren te herkennen. Op die manier kan het de intentie van die software gedeeltelijk achterhalen.
Reflectie in verschillende programmeertalen, maakt gebruik van zichzelf. De taal Self is zelfs gebaseerd daarrond.

Verder is het begrijpen van problemen belangrijker dan ge denkt. Zo zijn er problemen die wel beslisbaar zijn, maar toch niet geïmplementeerd kunnen worden. En ja, dat kunnen praktische problemen zijn, bijvoorbeeld een probleem dat zegt dat een reeks van getallen gemakkelijk te vermenigvuldigen is. Maar stel nu een reeks van 100 getallen voor waarvan elk getal erg groot is?

NeverwinterX · 15 nov 2010

Cycloon zei:
Maar ook als je een programma schrijft dat oneindig blijft doorgaan heb je software geschreven die het probleem beschrijft. Dat een stuk software niet zomaar een ander stuk software kan analyseren is een feit, dat is net zoals het probleem dat een mens nooit zal kunnen zien of er vertakkingen zijn in de 4de dimensie. Tenzij je een observator bent van een hoger niveau zal je nooit een probleem kunnen oplossen dat zich stelt in een ander niveau (of je eigen niveau). Maar dat zijn louter theoretische problemen, omdat wij die "problemen" zelf zien, maar ze er in wezen nooit zullen zijn voor de software. Het halting probleem stelt zich wel degelijk op het niveau van een software-niveauprobleem en niet op een mens-niveauprobleem.

Geef mij één praktisch probleem dat zich stelt in het bedrijfsleven dat niet in software zou kunnen uitgedrukt worden. Software schrijven om de uitvoering van een ander stuk software te analyseren zonder specifieke input van dat 2de stuk software te definiëren is iets wat in praktijk nooit zal gevraagd worden. Vermits de TS het heeft over een dergelijk praktisch probleem zal er stééds een stuk software geschreven kunnen worden die zijn probleem kan verwerken. Wie het tegendeel beweerd moet dringend van achter de boeken komen!

Hangt er maar vanaf wat je bedoelt met "software die het probleem beschrijft" bedoelt. De definitie die je hanteert lijkt nergens op en pas je aan zodat het voor jouw argument goed uitkomt. Een programma dat voor vele inputs in oneindige loop gaat, zal voor niemand goed genoeg zijn.
En het wordt wel in de praktijk gevraagd want het zou een handige feature zijn voor alle IDE's (maar het is dus bewezen onmogelijk op TM's). Maar dat soort problemen komen niet zo vaak voor nee.

Cycloon · 15 nov 2010

Gurdt zei:
Er bestaan thans heel bekende stukken software die zichzelf gebruiken, vele virussen bijvoorbeeld.
Een anti-virusprogramma analyseert op zijn beurt stukken software om structuren te herkennen. Op die manier kan het de intentie van die software gedeeltelijk achterhalen.
Reflectie in verschillende programmeertalen, maakt gebruik van zichzelf. De taal Self is zelfs gebaseerd daarrond.

Verder is het begrijpen van problemen belangrijker dan ge denkt. Zo zijn er problemen die wel beslisbaar zijn, maar toch niet geïmplementeerd kunnen worden. En ja, dat kunnen praktische problemen zijn, bijvoorbeeld een probleem dat zegt dat een reeks van getallen gemakkelijk te vermenigvuldigen is. Maar stel nu een reeks van 100 getallen voor waarvan elk getal erg groot is?

Je kan software tot op een zeker niveau wel andere software laten analyseren, maar dat gaat altijd over beperkte repetitieve stukken herkennen. Het zal nooit zo ver komen dat een stuk software de volledige uitwerking van een ander stuk software zal kunnen doorgronden. Inclusief alle mogelijke input. Anti-virussoftware is ook héél beperkt in zijn kunnen, veel logica daarvan werd uiteindelijk gecodeerd door mensen.

NeverwinterX zei:
En het wordt wel in de praktijk gevraagd want het zou een handige feature zijn voor alle IDE's (maar het is dus bewezen onmogelijk op TM's). Maar dat soort problemen komen niet zo vaak voor nee.

Een andere handige feature voor een IDE zou zijn dat deze zelf code zou kunnen testen. Of nog beter, dat die zelf de code zou kunnen schrijven! Al die problemen komen bij mij onder de noemer van theoretische problemen, omdat ze in werkelijkheid totaal geen betekenis hebben.

Gurdt · 15 nov 2010

Cycloon zei:
Je kan software tot op een zeker niveau wel andere software laten analyseren, maar dat gaat altijd over beperkte repetitieve stukken herkennen. Het zal nooit zo ver komen dat een stuk software de volledige uitwerking van een ander stuk software zal kunnen doorgronden. Inclusief alle mogelijke input. Anti-virussoftware is ook héél beperkt in zijn kunnen, veel logica daarvan werd uiteindelijk gecodeerd door mensen.

Dus omdat een virusscanner niet de volledige software checkt zegt gij maar: "dat gaat nooit zover komen". Da weet gij toch nie? Misschien wil ik een programma dat dat wel doet :/ En dan weet ik dat dat niet gaat. Gij zegt gewoon "goh ja dit is in de praktijk, dus da moet gaan, want elk programma dat iemand ooit nodig zou kunnen hebben, is te programmeren".

En uiteraard wordt logica bepaald door mensen. Dah.

Cycloon zei:
Een andere handige feature voor een IDE zou zijn dat deze zelf code zou kunnen testen. Of nog beter, dat die zelf de code zou kunnen schrijven! Al die problemen komen bij mij onder de noemer van theoretische problemen, omdat ze in werkelijkheid totaal geen betekenis hebben.

Theoretische problemen. Tot er iemand komt die een heuristiek schrijft voor zulke dingen. Dan zult ge wel blij zijn. De theorie is er voor de praktijk, onthoud dat goed he, een computer zoals wij ze kennen bestaat in de eerste plaats, omdat men theoretische problemen wilde oplossen.

Ik denk echt dat gij de enige IT'er zijt die vindt dat theoretische problemen niets te betekenen hebben voor de werkelijkheid.

MAXXUR · 15 nov 2010

Cycloon zei:
Geef mij één praktisch probleem dat zich stelt in het bedrijfsleven dat niet in software zou kunnen uitgedrukt worden.

Hier is de specificatie A van een bakoven in een grote fabriek. Bewijs dat deze bakoven nooit eigenschap E zal vertonen met een programma dat true teruggeeft in het positieve geval, anders false.

GTFO

Cycloon · 15 nov 2010

Gurdt zei:
Ik denk echt dat gij de enige IT'er zijt die vindt dat theoretische problemen niets te betekenen hebben voor de werkelijkheid.

En zo zie je maar dat er met jou totaal niet te discussiëren valt. Ik heb nergens vermeld dat theoretische informatica onbelangrijk is, daar gaat de discussie zelf totaal niet over. Ik ben bijna zeker dat mijn theoretische kennis groter is dan die van jou, alleen hoef ik daar niet in elke post die ik maak over te pronken. Laat staan dat ik telkens weer de discussie moet proberen te winnen door te vertellen dat andere mensen er niks van kennen.

Get real en kom eens van achter je boeken om ook eens de praktische wereld daar buiten te leren kennen.

MAXXUR · 15 nov 2010

Ej reageer nu ook ens op mijn post?

Mijn mening is dus: er zijn dus écht wel een heel pak problemen die ge ni kunt algoritmisch oplossen, gestaafd met mijn voorbeeldje. 't Feit da ge daar ni vaak van hoort is da ge der geen algoritme voor kunt schrijve en dus ni veel implementaties kent hein

hein

Gurdt · 15 nov 2010

Cycloon zei:
En zo zie je maar dat er met jou totaal niet te discussiëren valt. Ik heb nergens vermeld dat theoretische informatica onbelangrijk is, daar gaat de discussie zelf totaal niet over.

Ik ga je een paar keer quoten.

"Al die problemen komen bij mij onder de noemer van theoretische problemen, omdat ze in werkelijkheid totaal geen betekenis hebben."

"Vermits de TS het heeft over een dergelijk praktisch probleem zal er stééds een stuk software geschreven kunnen worden die zijn probleem kan verwerken. Wie het tegendeel beweerd moet dringend van achter de boeken komen!"

"Maar dat zijn louter theoretische problemen, omdat wij die "problemen" zelf zien, maar ze er in wezen nooit zullen zijn voor de software."

"Ok ja, voor enkele theoretische problemen kan je niet zomaar generieke code schrijven die altijd zijn werk zal doen. Voor elk probleem dat zich in de realiteit stelt kan je wel een oplossing bedenken."

"Als je de oplossing van een realistisch probleem kan definiëren dan kan je altijd wel een programma schrijven die alle mogelijke oplossingen gaat aftoetsen. Vermits er zich in onze wereld nog steeds geen problemen hebben voorgedaan waarbij je de oplossing niet éénduidig kan beschrijven besluit ik dus dat er voor elk realistisch probleem een oplossing te programmeren valt."

Cycloon zei:
Ik ben bijna zeker dat mijn theoretische kennis groter is dan die van jou, alleen hoef ik daar niet in elke post die ik maak over te pronken. Laat staan dat ik telkens weer de discussie moet proberen te winnen door te vertellen dat andere mensen er niks van kennen.

Ik pronk daar niet mee. Ik vertel het gewoon wanneer anderen iets vertellen wat foutief is. En ja, dat jij een grotere kennis daarin hebt is wel duidelijk

ook uit bovenstaande quotes van jou. Waarom denk je trouwens dat jouw kennis in de theoretische informatica groter is? Enfin, hebt gij überhaupt ooit van een Turing-machine of beslisbaarheid gehoord? Uit jouw posts is dat alleszins niet duidelijk...

Cycloon zei:
Get real en kom eens van achter je boeken om ook eens de praktische wereld daar buiten te leren kennen.

I rest my case...

dJeez · 15 nov 2010

Gurdt zei:
Je kan bv onmogelijk programmeren wat de beurs morgen zou gaan doen, namelijk omdat dat afhangt van variabelen die we momenteel niet kunnen omzetten naar een eenduidige definitie.

Toch wel vrij accuraat, op basis van Twitter berichten, een Belg(!) heeft dat onlangs nog bewezen (even buiten beschouwing gelaten dat het louter toevallig was) : deredactie.be

.

PinkyNTheBrain · 16 nov 2010

Gurdt zei:
Bedoelt hij met de optimale oplossing, het meest optimale algoritme? Of gewoon de meest optimale verdeling van dozen? Die kan je namelijk vinden door elke mogelijke set van plaatsingen te genereren en daar de beste uit te kiezen, wel erg inefficiënt maar wel mogelijk

Het meest optimale algoritme denk ik.

MilM zei:
@topicstarter:

wat is de bedoeling van stap 2 precies?
"Stap 2: Neem de volgende doos in rij met de laagste density (Gewicht/Volume)"

Ik zou eerder verwachten dat de dozen die meer wegen (bij eenzelfde volume) eerst aan bod komen? (anders kun je op het einde voor het laatste schap overblijven met alle zware dozen en moet je terugkeren om dozen te verwijderen en opnieuw te beginnen)

-) Gelden de gewichtsrestricties enkel op niveau van schappen of zijn er meer restricties zoals dat een doos met een bepaald gewicht maar zoveel kg dozen bovenop hem kan dragen?
-) Mag je een grotere doos bovenop een kleinere plaatsen (groter zoals in dieper of breder)?

Met stap 2 hebben we gewoon gewerkt om het meeste volume voor het laagste gewicht in het rek te krijgen. Aangezien we toch nooit de volle 100 dozen in het rek krijgen, leek ons dat de beste oplossing

-)Gewichtsrestricties alleen op niveau van de schappen ja.
-) Dat mag ja, alleen zit je dan met verspilde plaats (en dat lijkt mij altijd wel het geval dat je met enige verspilling zit)

Albireo zei:
Het is een interessant probleem. Mag je dozen roteren? En moeten de stapels dozen keurig naast mekaar staan of mag je dozen uit naburige stapels in mekaar schuiven alsof het een 3D tretis spel is? Dat zijn 2 mogelijkheden die het aantal mogelijke oplossingen gigantisch doen toenemen.

Hoedanook, ik zou i.p.v. een algoritme proberen te schrijven dat een zo goed mogelijke oplossing geeft een algoritme maken dat gedurende een beperkte tijd willekeurige oplossingen berekent en daaruit de beste kiest. Ik zou wel proberen wat optimalisaties proberen in te bouwen, bv eerst de zwaarste dozen gelijkmatig over alle rekken verdelen.

Dozen mogen gedraaid worden hoe je wil... dat van het 3d tetris spel denk ik niet dat mag nee.

En dat algoritme dat jij voorstelt is wel mooi. Maar dat lijkt me moeilijk uit te schrijven

(we moeten eerst een geschreven methode voorleggen en daarna pas programmeren)

voltje · 16 nov 2010

Albireo zei:
Hoedanook, ik zou i.p.v. een algoritme proberen te schrijven dat een zo goed mogelijke oplossing geeft een algoritme maken dat gedurende een beperkte tijd willekeurige oplossingen berekent en daaruit de beste kiest.

Zoals ik al zei, backtracking.

Archief - Vraagje of dit mogelijk is

Gurdt

Legacy Member

Gurdt

Legacy Member

MilM

Legacy Member

voltje

Legacy Member

Gurdt

Legacy Member

MilM

Legacy Member

nguaroth

Legacy Member

Albireo

Legacy Member

Cycloon

Legacy Member

Gurdt

Legacy Member

NeverwinterX

Legacy Member

Cycloon

Legacy Member

Gurdt

Legacy Member

MAXXUR

Legacy Member

Cycloon

Legacy Member

MAXXUR

Legacy Member

Gurdt

Legacy Member

dJeez

Legacy Member

PinkyNTheBrain

Legacy Member

voltje

Legacy Member