Kan de simulatie krachtiger zijn dan de simulator?

quote:

Op vrijdag 19 november 2004 23:20 schreef Oud_student het volgende:
Nee

Jawel. Een Turingmachine T1 is een logischl 'apparaatje' dat een bepaald algoritme uit kan voeren met een bepaald alfabet, gegeven een bepaalde input. Een Universele Turingmachine U is een Turingmachine T2 die onder andere T1 kan simuleren. Sterker, een U kan elke T simuleren, vandaar de naam 'universeel'. Dat heeft niets te maken met oneindigheden of niet. Een computer kan elk willekeurig in zijn alfabet (taal) geschreven programma uitvoeren gegeven een bepaalde input (data), en is dus een U.

quote:

Op zich juist, maar er is wel zo iets als operatie en overgang van de ene naar de andere toestand.
Hoeveel van die operaties (N) nodig zijn voor een berekening wordt idd in het midden gelaten, dwz.
het kan elk natuurlijk getal N zijn.
Mijn computer heeft wegens zijn snelheid en beperkte levensduur een bepekt aantal operaties
zeg 30 jaar = 10⁹ sec en snelheid 10⁹ Hz
dus ongeveer 10¹⁸ operaties
Er zijn makkelijk wiskundige problemen denkbaar die 10¹⁰⁰⁰ operaties vereisen.

Leuk, maar dat maakt het niet minder een universele Turingmachine.

quote:

Nee, een Turingmachine met beperkt geheugen (tape) is minder sterk dan een met onbeperkt geheugen, dwz er is een klasse van problemen (zelfs oneindig groot) die de een wel kan oplossen en de ander niet.

Dat klopt, maar er is altijd een grotere computer beschikbaar

quote:

Op vrijdag 19 november 2004 23:25 schreef Doffy het volgende:
Jawel. Een Turingmachine T1 is een logischl 'apparaatje' dat een bepaald algoritme uit kan voeren met een bepaald alfabet, gegeven een bepaalde input. Een Universele Turingmachine U is een Turingmachine T2 die onder andere T1 kan simuleren. Sterker, een U kan elke T simuleren, vandaar de naam 'universeel'. Dat heeft niets te maken met oneindigheden of niet. Een computer kan elk willekeurig in zijn alfabet (taal) geschreven programma uitvoeren gegeven een bepaalde input (data), en is dus een U.

De (een) Universele Turingmachine U heeft een beperkt aantal toestanden (ik ken een oplossing met ongeveer 120 toestanden). Om een Turing machine met een willekeurig aantal toestanden te kunnen simuleren, gebruikt U een codering om de 5-tupels (T1,T2, letter1,letter2, richting) op te slaan op tape. Daarom alleen al heeft U een onbeperkte hoeveelheid tape nodig. Daar komt bij, dat gedurende de berekening (simulatie van een willekeurige Turingmachine) ook niet van te voren bekend is hoeveel geheugen er nodig is.
Het oneindigheids aspect (liever het onbegrensd zijn) van het geheugen is juist de essentie van de Turingmachine

quote:

Leuk, maar dat maakt het niet minder een universele Turingmachine.

Een computer is inzoverre "universeel" , dat hij elk programma (of elke turingmachine) kan uitvoeren, die binnen zijn geheugen capaciteit en het aantal proces stappen (10^20 bijv) uitvoerbaar zijn, dus een zeer kleine klasse van alle berekenbare functies (0%)
Verre van Universeel

quote:

Dat klopt, maar er is altijd een grotere computer beschikbaar

Dit gaat niet helpen. Er zijn al programmaatjes van een paar regels te bedenken, die een Fysieke computer nooit zal kunnen uitvoeren (in de zin van succesvol met antwoord) terwijl de Turingmachine het wel kan, domweg omdat er te weinig materie en uitvoeringstijd in het heelal is om zo'n systeem te kunnen laten werken

Om op de originele vraag terug te komen, nee, een simulatie kan niet krachtiger zijn dan zijn simulator. Stel je hebt een simulator A₁ die Simulatie B₁ draait en Simulatie B₁ simuleert een simulator A₂, waar A₂ gelijk is aan A₁, dan zou dit betekenen dat A₂ een simulatie B₂ simuleert, die weer een simulator A₃ simuleert, etc. Dit zou betekenen dat simulator A₁ oneindig veel geheugencapaciteit en rekenkracht moet hebben, immers een simulatie die iets simuleert, simuleert dit niet opeens buiten het systeem.

quote:

Op zaterdag 20 november 2004 12:53 schreef Oud_student het volgende:
Het oneindigheids aspect (liever het onbegrensd zijn) van het geheugen is juist de essentie van de Turingmachine

Het onbegrenst-zijn is een verschil tussen een abstracte Turingmachine en een concrete (=computer), maar het is zeker geen essentie van Turingmachines.

quote:

Een computer is inzoverre "universeel" , dat hij elk programma (of elke turingmachine) kan uitvoeren, die binnen zijn geheugen capaciteit en het aantal proces stappen (10^20 bijv) uitvoerbaar zijn, dus een zeer kleine klasse van alle berekenbare functies (0%)
Verre van Universeel

Jij praat over een anders soort universaliteit dan ik. Ik heb het over een Universele Turingmachine, en dat is een Turingmachine die alle andere Turingmachines kan simuleren. Dat zegt niets over het kunnen oplossen van alle problemen, want er zijn inderdaad problemen die oneindige tijd en/of geheugen nodig hebben. Dat zijn problemen die sowieso niet oplosbaar zijn, ook niet op een Turingmachine. In die zin is geen enkele Turingmachine, laat staan elke computer, universeel. Maar dat is een ander soort universaliteit.

quote:

Dit gaat niet helpen. Er zijn al programmaatjes van een paar regels te bedenken, die een Fysieke computer nooit zal kunnen uitvoeren (in de zin van succesvol met antwoord) terwijl de Turingmachine het wel kan, domweg omdat er te weinig materie en uitvoeringstijd in het heelal is om zo'n systeem te kunnen laten werken

Als er een Turingmachine T bestaat die een probleem P kan oplossen in eindige tijd, dan kan er een computer gebouwd worden (+programma geschreven worden) die dat probleem oplost, in eindige tijd en eindig geheugen. Als een T oneindig lang over een P zou doen (bijvoorbeeld het halting problem) dan kan je met de beste wil van de wereld niet zeggen dat T het probleem wél oplost.

quote:

Op maandag 22 november 2004 10:16 schreef Doffy het volgende:
Het onbegrenst-zijn is een verschil tussen een abstracte Turingmachine en een concrete (=computer), maar het is zeker geen essentie van Turingmachines.

Je zou natuurlijk zelf eens in een boek kunnen kijken ( 1 rude is al meer dan genoeg)
Bijvoorbeeld van: http://plato.stanford.edu/entries/turing-machine/#Definition
In modern terms, the tape serves as the memory of the machine, while the read-write head is the memory bus through which data is accessed (and updated) by the machine. There are two important things to notice about the definition. The first is that the machine's tape is infinite in length, corresponding to an assumption that the memory of the machine is infinite. The second is similar in nature, but not explicit in the definition of the machine, namely that a function will be Turing-computable if there exists a set of instructions that will result in the machine computing the function regardless of the amount of time it takes. One can think of this as assuming the availability of infinite time to complete the computation.

quote:

Jij praat over een anders soort universaliteit dan ik. Ik heb het over een Universele Turingmachine, en dat is een Turingmachine die alle andere Turingmachines kan simuleren. Dat zegt niets over het kunnen oplossen van alle problemen, want er zijn inderdaad problemen die oneindige tijd en/of geheugen nodig hebben. Dat zijn problemen die sowieso niet oplosbaar zijn, ook niet op een Turingmachine. In die zin is geen enkele Turingmachine, laat staan elke computer, universeel. Maar dat is een ander soort universaliteit.

Ik praat over de universaliteit zoals door Turing zelf is gedefinieerd.
Alle problemen zijn idd niet oplosbaar = berekenbaar.
De universele Turingmachine is een turingmachine, die als input de codering van turingmachine X heeft + de input die voor X is bestemd.
Essentieel is, dat U elke turingmachine op deze wijze kan simuleren, dus alle berekenbare problemen

quote:

Als er een Turingmachine T bestaat die een probleem P kan oplossen in eindige tijd, dan kan er een computer gebouwd worden (+programma geschreven worden) die dat probleem oplost, in eindige tijd en eindig geheugen. Als een T oneindig lang over een P zou doen (bijvoorbeeld het halting problem) dan kan je met de beste wil van de wereld niet zeggen dat T het probleem wél oplost.

Ook weer de klepel en de klok.
Het halting probleem is juist een voorbeeld om aan te tonen dat niet alle functies berekenbaar zijn.
Onze eindige computers kunnen slechts 0% van alle berekenbare functies uitvoeren, hoe groot je de computer ook bouwt; zelfs wanneer hij zo groot als het heelal zou zijn.
Om een willekeurige berekenbare functie te kunnen uitvoeren is nu eenmaal onbegrensd geheugen en onbegrensd aantal proces-stappen (=tijd) nodig.

De hardware (processor) kan echter wel eindig zijn. Het was het idee van J von Neumann, dacht ik om det algoritme in het geheugen te plaatsen ipv (wat tot die tijd gebruikelijk was) elk probleem opnieuw hard-wired te programmeren.
De universele turing machine heeft ook een eindig aantal toestanden (bijv 120)
Het toestand-automaten gedeelte van de Turingmachine kunnen wij idd nabouwen in de werkelijke wereld, onbeperkt geheugen en processing power echter niet.

quote:

Op zaterdag 20 november 2004 18:02 schreef IvdSangen het volgende:
Om op de originele vraag terug te komen, nee, een simulatie kan niet krachtiger zijn dan zijn simulator. Stel je hebt een simulator A₁ die Simulatie B₁ draait en Simulatie B₁ simuleert een simulator A₂, waar A₂ gelijk is aan A₁, dan zou dit betekenen dat A₂ een simulatie B₂ simuleert, die weer een simulator A₃ simuleert, etc. Dit zou betekenen dat simulator A₁ oneindig veel geheugencapaciteit en rekenkracht moet hebben, immers een simulatie die iets simuleert, simuleert dit niet opeens buiten het systeem.

Het kan in zekere zin toch:
denk maar aan de Drosteverpleegster


Zij houdt in haar hand een blik met daarop een verpleegster die een blik in haar hand houdt met ..etc

(zie ook verder op de site van univ Leiden over Escher en een tekening die zichzelf bevat !)

quote:

Op maandag 22 november 2004 11:26 schreef Oud_student het volgende:
Het kan in zekere zin toch:
denk maar aan de Drosteverpleegster
[afbeelding]

Zij houdt in haar hand een blik met daarop een verpleegster die een blik in haar hand houdt met ..etc

(zie ook verder op de site van univ Leiden over Escher en een tekening die zichzelf bevat !)

Maar niet elke verpleegster is even gedetailleerd.

quote:

Op maandag 22 november 2004 11:49 schreef P-Style het volgende:
Maar niet elke verpleegster is even gedetailleerd.

Je moet het zin als wiskundig object.
Het is een oneindige verzameling (fractal) van telkens dezelfde afbeelding op steeds kleinere schaal.
Stelling: Elke compacte oneindige verzameling heeft een verdichtingspunt.
Van wie is deze stelling ?

quote:

Op maandag 22 november 2004 11:15 schreef Oud_student het volgende:
Je zou natuurlijk zelf eens in een boek kunnen kijken ( 1 rude is al meer dan genoeg)

quote:

Op maandag 22 november 2004 12:57 schreef Doffy het volgende:

Ik zie dat je gelijk naar de bibliotheek bent gegaan, prima zaak !