Newsgroup: it.comp.ia
Titolo: Il nastro di un LBA e' infinito o no?

che lo computa (infinito in potenza ma non in atto)
Proprio cosi': *un* CSL corrisponde a *un* LBA. Secondo la tua
versione, dato un CSL, ci vorrebbe un LBA con nastro lungo 1 per
riconoscere le stringhe di 1 carattere; un altro con nastro lungo 2;
un altro ancora con nastro 3;....
Cioe' non un solo LBA, ma infiniti. Ribadisco: il _solo_ LBA
corrispondente al CSL deve avere nastro infinito. Ciao

: 
Linearmente limitato rispetto all'input significa che sta in Ki, dove i e' 
la dimensione dell'input.
Quindi, tutto dipende dalla dimensione dell'input - e dal device che si 
usa. Per esempio, usando una random access machine, l'input e' definito 
come un *programma* arbitrariamente lungo ma finito. 
Il che significa che la macchina usera' sempre una porzione arbitrariamente 
lunga ma finita di memoria per eseguire la computazione.
Usando una macchina di turing universale, ad esempio, l'input viene scritto 
su nastro prima di iniziare la computazione - quindi se e' infinito la MdTU 
non parte nemmeno.
-- 
God is Real, unless declared Integer.
ObjectZone - 
http://space.tin.it/computer/csadun

non parte nemmeno.
Penso che un input infinito non abbia interesse in questo contesto. Si
stava discutendo di input finiti ma arbitrariamente lunghi. Questi
necessitano IMHO di un dispositivo di input infinito. Ciao

limite superiore? 
Si', infatti. Il device di input dev'essere largo a sufficienza, che e' a dire 
non limitato almeno in una direzione. 


 non limitato almeno in una direzione. 
Ci riprovo un`altra volta. Il device di input deve essere lungo
un tot in proporzione alla grandezza dell`input, ma effettivamente
una macchina reale che riconoscesse tutti i csl dovrebbe avere
nastro infinito.
Ora la tesi era che i computer reali computassero dei linguaggi
cs non semplicemente quelli regolari (asf) questo perche` 
(come ho scritto piu` volte)
*un computer reale finito ovvero in cui la lunghezza massima del
nastro sia stata decisa una volta per sempre, puo` computare
un *sottoclasse* dei csl possibili, di fatto pero` i linguaggi
riconosciuti/computati sono cs e *non* solo regolari.
ripeto un`altra volta
per ogni csl esiste un lba finito (con nastro finito) che lo
computa.
per ogni lba finito esiste un sotto insieme di csl che possono
essere computati.
Non esiste un sistema reale a nastro infinito, cioe` non e` 
costruibile, ma questa e` un` altra faccenda.
iao R.
-- 
E-Mail 
rc37...@silab.dsi.unimi.it
 | "CARLO HA TORTO: QUESTA E` LA MIA FEDE"
Roberto Corda, detto anche Coso    | "Gli ultimi esami non finiscono mai"

costruibile, ma questa e` un` altra faccenda.
In effetti ci stavo pensando proprio qualche tempo fa.
Nastro infinito, ovviamente no - ma nel senso delle computazioni a memoria 
limitata, tutto quel che abbiamo bisogno - una volta nota la dimensione 
dell'input - e' nastro "abbastanza lungo".
Il che significa che, dato un input di dimensione K - se abbiamo *sempre* la 
possibilita' di *aggiungere nastro* fino a K+LK (che in un computer vero 
significa essenzialmente aggiungere memoria), allora e' sempre possibile 
costruire un computer reale (opportunamente "scalato") equivalente etc...
Ora, certo non sono esperto di hardware, ma oggi come oggi mi pare che anche se 
un processore solo con le varie architetture in giro fosse sempre limitato ad 
un certo spazio di indirizzamento, finito, aggiungendo processori, e 
dedicandone uno a "controller", si ottengono spazi di indirizzamento 
virtualmente illimitati, a prezzo di overhead di costruzione e collegamento e, 
a runtime, di "traduzione" di indirizzi - cioe' complessita' spaziale e  
temporale.
Alla fine della fiera ovviamente il tutto e' limitato dalla disponibilita' di 
processori - cioe' dalla quantita' di silicio (o qualunque siano i materiali 
usato per costruire processori, fili, etc ) presente nell'universo.
Se l'universo ha dimensione (e risorse) limitate, allora non e' sempre possible 
costruire un computer equivalente ad una certa macchina logica.. altrimenti 
si'. Hm. :) 


costruibile, ma questa e` un` altra faccenda.
Forse l'equivoco si origina dal fatto che per un ASF che deve
riconoscere un linguaggio regolare non e' necessario un vero e proprio
device di input. Cioe' l'ASF in questione legge una lettera alla volta
della stringa d'input, senza la necessita' di memorizzare le
precedenti lettere lette se non attraverso una transizione in una
gamma finita di stati. In questo modo e' possibile leggere una stringa
finita (ma senza un limite superiore di) caratteri, accettarla o
rifiutarla. In un LBA le cose vanno in modo differente: tutta la
stringa deve essere presente sul nastro, che funge sia da device di
input che di elaborazione. Cioe' l'input non puo' essere bufferizzato
come in un ASF. Far passare l'input in un buffer di lunghezza finita
significherebbe trasformare l'LBA in un ASF. Ciao

 si'. Hm. :)
L-altra possibilita` e` avere un dispositivo finito con infiniti stati
distinguibili,
ma non credo sia costruibile.. o si`?
Ciao R.

 tipo a^n b^n (insieme non regolare).
Non si puo`.
Ciao R.


Non si puo`.
E allora l'LBA a nastro finito *non* riconosce il CSL a^n b^n, punto e
basta. Non ha senso dire che riconosce solo una parte di un CSL.
Riprendendo la discussione dall'inizio, dire che il nastro di un LBA
e' finito non e' meno scorretto che affermare che lo stack di un
automa a pila e' finito. Ciao

 automa a pila e' finito. Ciao
mmh..


>riconosce aaba..
Non riconosce aaba. 6 non e' stato terminale. Ciao

Robbè, scusami ma secondo me l'amico filibustero tiene ragione, forse ha
fatto un po' di casino nel disegnare l'automa, del resto in formato testo
non è semplicissimo, ma a^n b^n se n è limitato superiormente diventa
regolare ed è facile disegnare l'automa a stati finiti che lo riconosce,
che dovrebbe avere 2N+2 stati, dove N è il max n ammesso.
Ci provo:
[0]-a->[1]-a->[2]-a->[3]-a->[4]-a-> ... -a->[N]
           |         |         |         |                     |
           b        b        b        b                     b
           |         |         |         |                     |
           \/        \/       \/         \/                   \/
          [F]<-b-[1]<-b-[2]<-b-[3]<-b- ...<-b-[N-1]
insomma ci sono due file di stati, una ascendente che conta le a e una
discendente che conta le b, [0] ed [F] sono stati finali, per input diversi
da quelli segnati si va in uno stato trappola e li si rimane, non so se mi
sono capito...
   Gg.

Mi sono scordato di dire che [0] è lo stato di partenza.
Penso sia lo stesso automa che ha indicato el filibustero.
E comunque, per quello che mi ricordo (esame dato due mesi fa, vergognoso),
un LBA ha nastro infinito, scritto un input qualsiasi sul nastro l'automa
utilizza una parte finita del nastro (diciamo che gli basta il doppio della
lunghezza dell'input) per cercare di riconoscerlo, questo implica la
ricorsività del linguaggio riconosciuto.
  Gg.
PS: per Roberto: magari rispondi alle mail...

 sono capito...
Si e difatti e l`automa che intendeva il pirata..
Non sono ancora sicuro della generalita` della cosa... 
se questo e` vero a che serve la teoria della computabilita`?
Stiamo parlando di fantasmi?
iCiao R.
