Senda inn spurningu
Sólin Sólin Rís 05:12 • sest 21:41 í Reykjavík
Tunglið Tunglið Rís 00:00 • Sest 00:00 í Reykjavík
Flóð Flóð Árdegis: 08:09 • Síðdegis: 20:27 í Reykjavík
Fjaran Fjara Árdegis: 02:12 • Síðdegis: 14:14 í Reykjavík
Visit the English version

Flokkun:

Náttúruvísindi og verkfræði Tölvunarfræði
Náttúruvísindi og verkfræði Stærðfræði

Ef maður gerir talnarunu, til dæmis 1, 8, 30 ..., er þá alltaf einhver regla sem býr til rununa?

Gunnar Þór Magnússon

Í fyrstu gæti okkur þótt svarið við þessari spurningu augljóst; ef hægt er að hugsa sér einhverja runu, þá ætti að vera hægt að finna reglu sem býr hana til. En ef við veltum spurningunni aðeins betur fyrir okkur, þá kemur í ljós að svarið við henni er alls ekki ljóst. Hugmyndir stærðfræðinnar um óendanleikann og raunverulegar takmarkanir tölvunarfræðinnar á hvað er hægt að reikna út og hvað ekki, hanga nefnilega á spýtunni. Áður en við svörum spurningunni sjálfri er vert að huga að því við hvað er átt með hugtökunum runur og reglur, en þegar því er lokið liggur svarið sjálft nokkuð beint við.

Dæmi um fall frá einu mengi í annað.

Talnarunur koma mikið við sögu í stærðfræði og menn hafa komið sér vel saman um hvernig skuli setja þær fram. Upphaflega spurningin tók dæmi um runu sem er bara með heiltölum, og það er ágætt að halda sig við þær, en ekkert í svarinu breytist þó við skoðum í staðinn raun- eða tvinntalnarunur. Runa, eða talnaruna, er fall frá náttúrlegu tölunum yfir í heiltölurnar. Það er hægt að sjá runur fyrir sér á marga vegu, til dæmis með því að gefa fallið sem svarar til rununnar, eða einkenna meðlimi hennar á einhvern annan hátt. Til dæmis eru

2, 4, 6, 8, 10, 12, 14, ... og
1, 4, 1, 5, 9, 2, 6, ...

báðar runur; sú fyrri er gefin með fallinu f(n) = 2n, en í þeirri seinni eru aukastafir pí taldir upp. Allar runur sem við munum skoða hafa óendanlega marga meðlimi. Það takmarkar okkur ekki, því ef við rekumst á einhverja runu sem tekur enda, þá getum við breytt henni í óendanlega runu með því að endurtaka síðustu töluna í henni að eilífu.

Þegar stærðfræðingar tala um óendanlegan fjölda gera þeir greinarmun á teljanlegum- og óteljanlegum óendanleika. Ef við eigum teljanlega marga hluti, þá þýðir það að við getum parað þá einn af öðrum með tölunum 1, 2, 3, ..., og fjöldi þeirra er endanlegur eða jafn fjölda náttúrlegu talnanna. Við getum hins vegar verið með það marga hluti að þeir eru fleiri en náttúrlegu tölurnar, og þá segjum við að fjöldi þeirra sé óteljanlegur. Sem dæmi eru sléttu tölurnar teljanlega margar, en rauntölurnar eru óteljanlega margar. Nú liggur auðvitað beint við að spyrja sig hvort til séu teljanlega eða óteljanlega margar runur?



Á þessari mynd eru teljanlega margir boltar.

Fljótséð er að það eru til óteljanlega margar mismunandi runur: Við fáum eina runu fyrir hverja náttúrlega tölu n með því að fara gegnum margföldunartöfluna fyrir n, eins og við gerðum hér að ofan þegar við settum n jafnt 2 og fengum sléttu tölurnar. Ef við hugsum okkur um í smástund sjáum við þó að það eru að minnsta kosti til jafn margar runur og rauntölur, því ef við höfum einhverja rauntölu getum við búið til rununa sem telur upp tölustafina í tugabrotaframsetningu rauntölunnar. Þar sem það eru til óteljanlega margar rauntölur, þá eru líka til óteljanlega margar runur.

En þá skulum við snúa okkur að reglunum. Við skulum segja að það sé til regla sem býr til runu ef það er hægt að láta tölvu gefa okkur tölurnar í rununni, því það samsvarar ágætlega þeim hugmyndum sem við höfum um reglur. Þá eru til reglur fyrir báðar runurnar okkar að ofan, því sú fyrri er einfaldlega gefin með formúlu, og ef við höfum nægan tíma þá er hægt að láta tölvu reikna eins marga aukastafi í pí og við viljum, og gefa þá einn af öðrum.

Þar sem það eru til margar mismunandi tölvur í dag, þá væri best að við kæmum okkur saman um hvernig tölvu við ætlum að nota. Í tölvunarfræði er oft notast við svokallaðar Turing-vélar þegar á að líkja eftir nútímatölvum, og þær henta ágætlega hér. Á meðan fræðilega skilgreiningin á Turing-vél er háð ýmsum smáatriðum, þá er einfalt að lýsa þeim með beinum orðum: Turing-vél er kassi sem flakkar fram og til baka á óendanlega löngum minnisborða, og getur bæði lesið tákn af honum, skrifað á hann, og breytt þeim táknum sem eru á borðanum.



Teikning listamanns af Turing-vél.

Sérhver Turing-vél er aðeins hönnuð til að vinna eitt verk. Þannig er til Turing-vél sem gerir ekkert annað en að leggja saman tvo og þrjá, önnur Turing-vél sem getur aðeins margfaldað gefna tölu með fimm, og aðrar sem vinna einhver flóknari verk. Við fyrstu sýn virðast þetta mjög einfaldar og takmarkaðar vélar, og því kemur flestum verulega á óvart að allt sem er hægt að gera með tölvum í dag má gera með Turing-vélum. Fyrir okkur þýðir þetta að við getum sagt að á bakvið gefna runu sé regla ef það er til Turing-vél sem gefur okkur tölurnar í rununni.

Þetta reynist vera lykilatriðið sem þarf til að svara upphaflegu spurningunni, því þegar maður skoðar formlegu skilgreininguna á Turing-vél kemur í ljós að það eru bara til teljanlega margar slíkar vélar. Við munum að það eru til óteljanlega margar runur, svo þar af leiðir að það eru til runur sem engin regla er á bakvið. Vegna þess að slíkar runur eru í eðli sínu mjög flókin fyrirbæri treystum við okkur þó ekki til að benda á dæmi um þannig runu hér. Þeir sem hafa áhuga á runum af þessu tagi ættu að kynna sér reiknanleika og reiknanleg föll í fræðilegri tölvunarfræði.

Frekara lesefni af Vísindavefnum:

Heimildir og myndir:

  • Carothers, N.L. Real analysis. Cambridge University Press, 1999.
  • Sipser, Michael. Introduction to the Theory of Computation. PWS Publishing, 1997.
  • Grein um reiknanleika af Wikipedia.
  • Allar myndir fengnar af Wikipedia.

Höfundur

Gunnar Þór Magnússon

Gunnar Þór Magnússon

stærðfræðingur

Útgáfudagur

10.10.2008

Spyrjandi

Jörgen Ágústsson

Efnisorð

Tilvísun

Gunnar Þór Magnússon. „Ef maður gerir talnarunu, til dæmis 1, 8, 30 ..., er þá alltaf einhver regla sem býr til rununa?“ Vísindavefurinn, 10. október 2008. Sótt 27. apríl 2024. http://visindavefur.is/svar.php?id=20784.

Gunnar Þór Magnússon. (2008, 10. október). Ef maður gerir talnarunu, til dæmis 1, 8, 30 ..., er þá alltaf einhver regla sem býr til rununa? Vísindavefurinn. Sótt af http://visindavefur.is/svar.php?id=20784

Gunnar Þór Magnússon. „Ef maður gerir talnarunu, til dæmis 1, 8, 30 ..., er þá alltaf einhver regla sem býr til rununa?“ Vísindavefurinn. 10. okt. 2008. Vefsíða. 27. apr. 2024. <http://visindavefur.is/svar.php?id=20784>.

Chicago | APA | MLA

Þessi síða notar vafrakökur Nánari upplýsingar

Ég samþykki
Spyrja

Sendu inn spurningu LeiðbeiningarTil baka

Hér getur þú sent okkur nýjar spurningar um vísindaleg efni.

Hafðu spurninguna stutta og hnitmiðaða og sendu aðeins eina í einu. Einlægar og vandaðar spurningar um mikilvæg efni eru líklegastar til að kalla fram vönduð og greið svör. Ekki er víst að tími vinnist til að svara öllum spurningum.

Persónulegar upplýsingar um spyrjendur eru eingöngu notaðar í starfsemi vefsins, til dæmis til að svör verði við hæfi spyrjenda. Spurningum er ekki sinnt ef spyrjandi villir á sér heimildir eða segir ekki nægileg deili á sér.

Spurningum sem eru ekki á verksviði vefsins er eytt.

Að öðru leyti er hægt að spyrja Vísindavefinn um allt milli himins og jarðar!

=

Senda grein til vinar

=

Ef maður gerir talnarunu, til dæmis 1, 8, 30 ..., er þá alltaf einhver regla sem býr til rununa?
Í fyrstu gæti okkur þótt svarið við þessari spurningu augljóst; ef hægt er að hugsa sér einhverja runu, þá ætti að vera hægt að finna reglu sem býr hana til. En ef við veltum spurningunni aðeins betur fyrir okkur, þá kemur í ljós að svarið við henni er alls ekki ljóst. Hugmyndir stærðfræðinnar um óendanleikann og raunverulegar takmarkanir tölvunarfræðinnar á hvað er hægt að reikna út og hvað ekki, hanga nefnilega á spýtunni. Áður en við svörum spurningunni sjálfri er vert að huga að því við hvað er átt með hugtökunum runur og reglur, en þegar því er lokið liggur svarið sjálft nokkuð beint við.

Dæmi um fall frá einu mengi í annað.

Talnarunur koma mikið við sögu í stærðfræði og menn hafa komið sér vel saman um hvernig skuli setja þær fram. Upphaflega spurningin tók dæmi um runu sem er bara með heiltölum, og það er ágætt að halda sig við þær, en ekkert í svarinu breytist þó við skoðum í staðinn raun- eða tvinntalnarunur. Runa, eða talnaruna, er fall frá náttúrlegu tölunum yfir í heiltölurnar. Það er hægt að sjá runur fyrir sér á marga vegu, til dæmis með því að gefa fallið sem svarar til rununnar, eða einkenna meðlimi hennar á einhvern annan hátt. Til dæmis eru

2, 4, 6, 8, 10, 12, 14, ... og
1, 4, 1, 5, 9, 2, 6, ...

báðar runur; sú fyrri er gefin með fallinu f(n) = 2n, en í þeirri seinni eru aukastafir pí taldir upp. Allar runur sem við munum skoða hafa óendanlega marga meðlimi. Það takmarkar okkur ekki, því ef við rekumst á einhverja runu sem tekur enda, þá getum við breytt henni í óendanlega runu með því að endurtaka síðustu töluna í henni að eilífu.

Þegar stærðfræðingar tala um óendanlegan fjölda gera þeir greinarmun á teljanlegum- og óteljanlegum óendanleika. Ef við eigum teljanlega marga hluti, þá þýðir það að við getum parað þá einn af öðrum með tölunum 1, 2, 3, ..., og fjöldi þeirra er endanlegur eða jafn fjölda náttúrlegu talnanna. Við getum hins vegar verið með það marga hluti að þeir eru fleiri en náttúrlegu tölurnar, og þá segjum við að fjöldi þeirra sé óteljanlegur. Sem dæmi eru sléttu tölurnar teljanlega margar, en rauntölurnar eru óteljanlega margar. Nú liggur auðvitað beint við að spyrja sig hvort til séu teljanlega eða óteljanlega margar runur?



Á þessari mynd eru teljanlega margir boltar.

Fljótséð er að það eru til óteljanlega margar mismunandi runur: Við fáum eina runu fyrir hverja náttúrlega tölu n með því að fara gegnum margföldunartöfluna fyrir n, eins og við gerðum hér að ofan þegar við settum n jafnt 2 og fengum sléttu tölurnar. Ef við hugsum okkur um í smástund sjáum við þó að það eru að minnsta kosti til jafn margar runur og rauntölur, því ef við höfum einhverja rauntölu getum við búið til rununa sem telur upp tölustafina í tugabrotaframsetningu rauntölunnar. Þar sem það eru til óteljanlega margar rauntölur, þá eru líka til óteljanlega margar runur.

En þá skulum við snúa okkur að reglunum. Við skulum segja að það sé til regla sem býr til runu ef það er hægt að láta tölvu gefa okkur tölurnar í rununni, því það samsvarar ágætlega þeim hugmyndum sem við höfum um reglur. Þá eru til reglur fyrir báðar runurnar okkar að ofan, því sú fyrri er einfaldlega gefin með formúlu, og ef við höfum nægan tíma þá er hægt að láta tölvu reikna eins marga aukastafi í pí og við viljum, og gefa þá einn af öðrum.

Þar sem það eru til margar mismunandi tölvur í dag, þá væri best að við kæmum okkur saman um hvernig tölvu við ætlum að nota. Í tölvunarfræði er oft notast við svokallaðar Turing-vélar þegar á að líkja eftir nútímatölvum, og þær henta ágætlega hér. Á meðan fræðilega skilgreiningin á Turing-vél er háð ýmsum smáatriðum, þá er einfalt að lýsa þeim með beinum orðum: Turing-vél er kassi sem flakkar fram og til baka á óendanlega löngum minnisborða, og getur bæði lesið tákn af honum, skrifað á hann, og breytt þeim táknum sem eru á borðanum.



Teikning listamanns af Turing-vél.

Sérhver Turing-vél er aðeins hönnuð til að vinna eitt verk. Þannig er til Turing-vél sem gerir ekkert annað en að leggja saman tvo og þrjá, önnur Turing-vél sem getur aðeins margfaldað gefna tölu með fimm, og aðrar sem vinna einhver flóknari verk. Við fyrstu sýn virðast þetta mjög einfaldar og takmarkaðar vélar, og því kemur flestum verulega á óvart að allt sem er hægt að gera með tölvum í dag má gera með Turing-vélum. Fyrir okkur þýðir þetta að við getum sagt að á bakvið gefna runu sé regla ef það er til Turing-vél sem gefur okkur tölurnar í rununni.

Þetta reynist vera lykilatriðið sem þarf til að svara upphaflegu spurningunni, því þegar maður skoðar formlegu skilgreininguna á Turing-vél kemur í ljós að það eru bara til teljanlega margar slíkar vélar. Við munum að það eru til óteljanlega margar runur, svo þar af leiðir að það eru til runur sem engin regla er á bakvið. Vegna þess að slíkar runur eru í eðli sínu mjög flókin fyrirbæri treystum við okkur þó ekki til að benda á dæmi um þannig runu hér. Þeir sem hafa áhuga á runum af þessu tagi ættu að kynna sér reiknanleika og reiknanleg föll í fræðilegri tölvunarfræði.

Frekara lesefni af Vísindavefnum:

Heimildir og myndir:

  • Carothers, N.L. Real analysis. Cambridge University Press, 1999.
  • Sipser, Michael. Introduction to the Theory of Computation. PWS Publishing, 1997.
  • Grein um reiknanleika af Wikipedia.
  • Allar myndir fengnar af Wikipedia.
...