» »

Nivo abstraktnega razmišljanja

Nivo abstraktnega razmišljanja

1
2
»

Thomas ::

> Se pa mi "zdi", da nisem turingov stroj. Tako grozno se sliši, če drugega ne.

To pa lahko neseš kar v Ložo.
Man muss immer generalisieren - Carl Jacobi

drejc ::

Dokler en komp ne strese Turingovga testa al pa podobne zadeve, ne bom vrjeu da sm TM.

Po sp. Moravcevi meji bi se to (da se stroj zave) mogl zgodit ze Blue Gene-u semizdi.
"Rise above oneself and grasp the world"
- Archimedes of Syracuse

gzibret ::

> Sej TM, ki se ustavi, ne rabi neskončnega traku.

TM POTREBUJE neskončni trak, da razreši vse probleme, ki jih je možno razrešiti z algoritmom. Po defaultu.
Vse je za neki dobr!

OwcA ::

TM POTREBUJE neskončni trak, da razreši vse probleme, ki jih je možno razrešiti z algoritmom. Po defaultu.

Zakaj?
Če pogledaš formalno definicijo, ni nikjer govora o kakšnih neskončnostih.
Tudi definicija algoritma je zelo finitno obarvana.
Otroška radovednost - gonilo napredka.

Zgodovina sprememb…

  • spremenilo: OwcA ()

gzibret ::

To bo treba popravit!

Tole: "A Turing machine has an infinite one-dimensional tape divided into cells." sem našel tu.

Tole: "a hypothetical computing machine that has an unlimited amount of information storage " pa tu (Webster online, še najbolj kredibilen vir).

Tole: "Turing Machine
A MODEL OF COMPUTATION that uses an underlying FINITE-STATE AUTOMATON but also has a infinite tape to use as memory. Turing machines are capable of UNIVERSAL COMPUTATION. " sem našel tu.

Tole: "Turing Machine An infinite loop of squares, containing either 0 or 1, passing through a device which can either change or retain that symbol. Such a machine can solve any problem which can be clearly stated (Alan Turing). " sem našel tu.

Tole: "S: (n) Turing machine (a hypothetical computer with an infinitely long memory tape) " sem našel tu.

Dovolj?
Vse je za neki dobr!

OwcA ::

Ne, ne bo. Najdi mi formalno definicijo.

Celo iz enega tvojega linka:
Talk of "tape" and a "read-write head" is intended to aid the intution (and reveals something of the time in which Turing was writing) but plays no important role in the definition of Turing machines.

čemur sledu formalna definicija brez omenjanja neskončnosti.
Otroška radovednost - gonilo napredka.

gzibret ::

Poglej definicijo iz Webstra in zadnji link. Mislim, da sta zello jasna. Pa tudi v večih knjigah (znanstvenih) sem bral o neskončnem traku.

Tisto, kar si izpostavil ti, nič ne govori o končnem traku (memoriji). Seveda turingova mašina reši ogromno problemov na končnem traku. Ne reši pa VSEH problemov, ki jih lahko reši algoritem, če nima neskončno spomina (traku ali karkoli že pač).
Vse je za neki dobr!

gzibret ::

Sicer pa tudi formalna definicija (iz Wikija) govori o nulah, katerih število je neomejeno (GAMA is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation) ).

Neskončen trak je dovoljen in če želimo rešiti vse probleme, ki jih lahko razreši računalnik, tudi potreben.
Vse je za neki dobr!

OwcA ::

Bolj univerzalne definicije od [1]
M = (S, G, b, Q, q0, qY, qN, d,?r,?m), je Turingov stroj. Pri tem je:
S ... Vhodna abeceda
G = S [ {b} [ ... Tračna abeceda
b ... Prazni znak
Q ... Množica stanj
q0 2 Q ... začetno stanje
qY, qN 2 Q ... Končni stanji: dobro, slabo
d: S L Q ! Q ... Prehodna funkcija
r: S L Q ! S ... Funkcija pisanja
m: S L Q ! {L, D, I} ... Funkcija pomika

ni.

Ja, ne govori o traku, ker trak je pomagalo, da si lažje predstavljamo.

Ni mi tudi jasno kako se ti lahko povsem splošen slovar zdi ultimativna referenca.

Neskončen trak je dovoljen in če želimo rešiti vse probleme, ki jih lahko razreši računalnik, tudi potreben.

Ja, je dovoljen, ni pa nujen, torej obstaja TS, ki s končnim trakom emulira tvojega z neskončnim.
Povej algoritem, ki dokazano za končen vhodni podatek potrebuje neskončen trak. Da ti pomagam, ga ni. Ker potem bi bodisi moral imeti neskončno stanj (-><- z definicijo TS) ali bi potreboval za izvajanje neskončno časa (-><- z definicijo algoritma).

[1] Pisanski, skripta za predmet Računalništvo, FMF 2004
Otroška radovednost - gonilo napredka.

Zgodovina sprememb…

  • spremenilo: OwcA ()

OwcA ::

Otroška radovednost - gonilo napredka.

mia- ::

protislovje se najde že ob najbolj trivialnem primeru.
Thomas namreč pravi, da si ne moreš izmislit postopka, ki se ne bi končal v končno korakih.

Recimo postopek: ki napiše število Pi, :
se ne konča v končno korakih, potrebuje neskočnno papirja.

Torej že to, da sm si js LAHKO zmislu to, za kar TS potrebuje neskončno časa in neskočnno papirja je v protislovju z trditvijo. Torej človekove zamisleke se nikoli ne bo dal opisat s finitnim TS.

sam kurc, eni pač dopuščajo protislovja, vse kar iz tega izhaja je pa kurc vredn

Thomas ::

> Thomas namreč pravi, da si ne moreš izmislit postopka, ki se ne bi končal v končno korakih.

Tega seveda nisem rekel, vendar je vseeno res. Živimo v končnem svetu.

> postopek: ki napiše število Pi, : se ne konča v končno korakih, potrebuje neskočnno papirja.

Seveda. Algoritem, ki se "v principu" nikoli ne konča, si lahko izmisliš. Noben problem. Vendar sam algoritem je definiran s končno znaki in v resnici se konča, v tem končnem svetu.


> Torej že to, da sm si js LAHKO zmislu to, za kar TS potrebuje neskončno časa

Potrebuje neskončno časa, da izvede. Da si pa algoritem izmisli, pa ne.

Eno je postopek, drugo je njegovo izvajanje. Postopek je lahko končno opisljiv, pa ni končno izvršljiv.

> sam kurc, eni pač dopuščajo protislovja, vse kar iz tega izhaja je pa kurc vredn

Nobenega protislovja ne dopuščam. Niti tistih navideznih, ki jih ti tako pridno konstruiraš.
Man muss immer generalisieren - Carl Jacobi

mia- ::

ah te finitisti :/
torej imate največjo številko? aja, dejte mi zaupat pa mi povejte katera je to.

ts rabi neskončno papirja.. zakaj?
Zato ker algoritmi lahko ponucajo poljubno veliko papirja.
Za vsako količino papirja, si lahko izmislimo algoritem, ki porabi več papirja.
torej potrebujemo tolk papirja, ki bo večje od vseh števil.
To je pa ravno definicija neskončnosti.

Thomas ::

> torej imate največjo številko? aja, dejte mi zaupat pa mi povejte katera je to.

Z veseljem. Samo ti prej napiši navečje možno, enolično in nedvoumno definirano naravno število, s tisoč ali manj znaki latinske abecede in ciframi od 0 do 9.

Ne moreš?

Boš rekel, da ne obstaja?
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

Thomas ::

Če ti bo kaj lažje, lahko uporabljaš še vse ASCII znake od 32. do 127.
Man muss immer generalisieren - Carl Jacobi

OwcA ::

torej imate največjo številko? aja, dejte mi zaupat pa mi povejte katera je to.

Ni poanta toliko v tem, da obstaja neko največje število (čeprav je v izoliranem sistemu tudi to res), ampak bolj v tem, da je ne voljo končno mnogo bitov s katerimi ga lahko opišemo. Brez težav lahko rečemo, da nam vsaka planckova dolžina pomeni nova fakulteta ali potenca, ampak neglede na vse bo ta opis končen.

Zato ker algoritmi lahko ponucajo poljubno veliko papirja. Za vsako količino papirja, si lahko izmislimo algoritem, ki porabi več papirja.

Ja lahko ga, ampak lahko ga pa prevedemo tudi na takšnega, ki ga ne, drugače to ne bi bil algoritem. Čim nujno rabiš neskončno traku, rabiš tudi neskončno korakov.
Priznam sicer, da se stvari zapletejo, če ostanemo v fizikalnem svetu in imamo zelo velike vhodne podatke, ker zaradi entropije potem postanejo stvari, ki so par miljard let nazaj bile izračunljive, neizračunljive, ampak tu se ne da kaj dosti pomagati, vsakekor ne bomo postorili nič več, če za TS zahtevamo neskončen trak.
Otroška radovednost - gonilo napredka.

Zgodovina sprememb…

  • spremenilo: OwcA ()

gzibret ::

Glede tele neskončnosti imamo zelo različna mnenja. Res potegne za sabo zelo veliko stvari....

Samo v matematiki je neskončnosti veliko. Zelo veliko. S pomočjo matematike pa opisujemo realni svet, a ne?

A je atomov v vesolju neskončno mnogo ali res zelo veliko, ampak vseeno končno mnogo. Ali je možnih planckovih dolžin neskončno mnogo ali končno mnogo..... IMO končno mnogo.

Ampak vse kombinacije interakcij med končno mnogo elementi da neskončno mnogo rezultatov. To pa imejmo v mislih.
Vse je za neki dobr!

Thomas ::

> Ampak vse kombinacije interakcij med končno mnogo elementi da neskončno mnogo rezultatov.

Dajo končno mnogo rezltatov.
Man muss immer generalisieren - Carl Jacobi

gzibret ::

Kak to, če lahko ima že neka enostavna funkcija neskončno periodo. Recimo tale:

X(n)=X(n-1)*(1-X(n-1))*4

Za poljuben začetni X(1) na intervalu od 0 do 1.

Ali pa tale:

Tn(x,y)=( sin(2un)+cos(3un),sin(un)-cos((un)^2) )

n=0..1
u=0..2*Pi

?
Vse je za neki dobr!

Thomas ::

Jah, kaj - nič.

Najprej, definira jo končno znakov. Da razčistimo najprej to, da ne bi bilo kaj nejasnega.

Potem, izvede se lahko le končno krat v tem svetu.

Če pa predpostavljaš Platonova nebesa - o tam pa ja! Tam imaš pa neskončno neskončnosti. Čeprav jih lahko definira le končno znakov. Ali pa tudi neskončno, če tako želiš.
Man muss immer generalisieren - Carl Jacobi
1
2
»


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Inforamtika-vprašanja

Oddelek: Šola
71789 (1647) seminal
»

Ustavljivost linearno omejenih avtomatov (strani: 1 2 )

Oddelek: Znanost in tehnologija
844742 (4256) Matevžk
»

Cantor, Russell ... Teorija množic. (strani: 1 2 3 )

Oddelek: Znanost in tehnologija
1439218 (7699) Odin
»

Turing train terminal

Oddelek: Novice / --Nerazporejeno--
473647 (2846) 64202
»

Alan Turing: izumitelj programske opreme

Oddelek: Novice / --Nerazporejeno--
92725 (2725) Tody

Več podobnih tem