$NN$ dall'alfabeto $\Sigma={0,1,2,3,4,5,6,7,8,9}$

[garnak.olegovitc1]

Salve a tutti,
di recente avevo intrapreso una discussione sui numeri naturali definiti con assiomi di Peano, conoscendo anche la definizione tramite insiemi... e sono pervenuto che :

$NN$[tex]\triangleq[/tex]${0,S(0),S(S(0)),S(S(S(0))),....}$

ove:

[tex]0[/tex]
[tex]1 \triangleq S(0)[/tex]
[tex]2 \triangleq S(S(0))[/tex] ovvero anche [tex]2 \triangleq S(1)[/tex]
[tex]3 \triangleq S(S(S(0)))[/tex] ovvero anche [tex]3 \triangleq S(2)[/tex]
[tex]4 \triangleq S(S(S(S(0))))[/tex] ovvero anche [tex]4 \triangleq S(3)[/tex]
[tex]5 \triangleq S(S(S(S(S(0)))))[/tex] ovvero anche [tex]5 \triangleq S(4)[/tex]
[tex]6 \triangleq S(S(S(S(S(S(0))))))[/tex] ovvero anche [tex]6 \triangleq S(5)[/tex]
[tex]7 \triangleq S(S(S(S(S(S(S(0)))))))[/tex] ovvero anche [tex]7 \triangleq S(6)[/tex]
[tex]8 \triangleq S(S(S(S(S(S(S(S(0))))))))[/tex] ovvero anche [tex]8 \triangleq S(7)[/tex]
[tex]9 \triangleq S(S(S(S(S(S(S(S(S(0)))))))))[/tex] ovvero anche [tex]9 \triangleq S(8)[/tex]
.
.
.

ora, la mia domanda è "io saprei continuare dopo il $9$, per esperienza, ma se io non avessi avuto l'esperienza dei miei studi come avrei potuto associare al [tex]S(9)[/tex] il numero $10$... e così via? Cioè esiste una qualche regola che possa venirmi in aiuto per il giusto simbolo?
Io, personalmente, ho subito pensato al concetto di linguaggio (in particolare, partendo da un alfabeto del tipo $ {0,1,2,3,4,5,6,7,8,9}$), stringa... ma non saprei dove pigliar pesci.
Ringrazio anticipatamente!!

Cordiali saluti

P.S.=Preciso, è una mia curiosità...

[garnak.olegovitc1]

Salve a tutti,
preciso e faccio alcune osservazioni dopo aver letto alcune cose, il mio scopo sarebbe quello di rappresentare l'insieme $NN$ dall'alfabeto ${0,1,2,3,4,5,6,7,8,9}$. Vedo che molti lo considerano:

http://www.ma.hw.ac.uk/~markl/teaching/AUTOMATA/kleene.pdf (esempi nella pg 2)
http://books.google.it/books?id=gqWMGR1otqoC&pg=PA32&dq=natural+numbers++considered+strings++alphabet&hl=it&sa=X&ei=MOb-T-6GNdCM4gSVx6XnBg&ved=0CDgQ6AEwAQ#v=onepage&q=natural%20numbers%20%20considered%20strings%20%20alphabet&f=false
http://www.win.tue.nl/~luttik/Courses/LV/handouts/StringsLanguages.pdf (pagina 1 e 2)

In quest'ultimo viene fatta una precisazione lecita, ovvero:

If $\Sigma = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$, then  contains all (names for) nat-
ural numbers. Note, however, that  contains more: it also contains the empty
string $epsilon$, and strings such as $007$ and $0402475142$ (i.e., strings with superfluous zeroes
at the beginning) that usually refer to other things than natural numbers.

come si potrebbe evitare che vi siano numeri/stringhe del tipo $007$ e $0402475142$ cioè senza che le prime cifre siano $0$, e che non vi sia la stringa vuota?
Ringrazio anticipatamente!

Cordiali saluti

P.S.=Preciso che forse l'argomento era meglio per la sezione informatica... aspetterò che venga spostato e scusatemi se ho sbagliato ma solamente ora me ne accorgo

[gundamrx91-votailprof]

Il fatto è che una stringa [tex]"0012"[/tex] non è un numero, seppure si possa convertire nel numero [tex]12[/tex], però ti ci vuole un algoritmo che poi andrebbe formalizzato in una proprietà che definisce [tex]\mathbb{N}[/tex]. Intanto credo che si debba partire dalla rappresentazione in base 10 dei numeri...

[garnak.olegovitc1]

Salve GundamRX91,

"GundamRX91":Il fatto è che una stringa [tex]"0012"[/tex] non è un numero, seppure si possa convertire nel numero [tex]12[/tex], però ti ci vuole un algoritmo che poi andrebbe formalizzato in una proprietà che definisce [tex]\mathbb{N}[/tex]. Intanto credo che si debba partire dalla rappresentazione in base 10 dei numeri...

grazie per l'intevento, pensavo che potrei eliminare subito la stringa vuota, secondo quanto scritto qui potrei considerare l'insieme non $\Sigma^**$ ma solamente $\Sigma^n$ con $n in NN - {0}$...

Però pensandoci, come faccio a scrivere $n in NN - {0}$ se ancora $NN$ non è stato definito? Accipicchia... devo trovare altre vie
Cordiali saluti

[Odexios]

"garnak.olegovitc":Salve a tutti,
di recente avevo intrapreso una discussione sui numeri naturali definiti con assiomi di Peano, conoscendo anche la definizione tramite insiemi... e sono pervenuto che :

$NN$[tex]\triangleq[/tex]${0,S(0),S(S(0)),S(S(S(0))),....}$

ove:

[tex]0[/tex]
[tex]1 \triangleq S(0)[/tex]
[tex]2 \triangleq S(S(0))[/tex] ovvero anche [tex]2 \triangleq S(1)[/tex]
[tex]3 \triangleq S(S(S(0)))[/tex] ovvero anche [tex]3 \triangleq S(2)[/tex]
[tex]4 \triangleq S(S(S(S(0))))[/tex] ovvero anche [tex]4 \triangleq S(3)[/tex]
[tex]5 \triangleq S(S(S(S(S(0)))))[/tex] ovvero anche [tex]5 \triangleq S(4)[/tex]
[tex]6 \triangleq S(S(S(S(S(S(0))))))[/tex] ovvero anche [tex]6 \triangleq S(5)[/tex]
[tex]7 \triangleq S(S(S(S(S(S(S(0)))))))[/tex] ovvero anche [tex]7 \triangleq S(6)[/tex]
[tex]8 \triangleq S(S(S(S(S(S(S(S(0))))))))[/tex] ovvero anche [tex]8 \triangleq S(7)[/tex]
[tex]9 \triangleq S(S(S(S(S(S(S(S(S(0)))))))))[/tex] ovvero anche [tex]9 \triangleq S(8)[/tex]
.
.
.

ora, la mia domanda è "io saprei continuare dopo il $9$, per esperienza, ma se io non avessi avuto l'esperienza dei miei studi come avrei potuto associare al [tex]S(9)[/tex] il numero $10$... e così via? Cioè esiste una qualche regola che possa venirmi in aiuto per il giusto simbolo?
Io, personalmente, ho subito pensato al concetto di linguaggio (in particolare, partendo da un alfabeto del tipo $ {0,1,2,3,4,5,6,7,8,9}$), stringa... ma non saprei dove pigliar pesci.
Ringrazio anticipatamente!!

Cordiali saluti

P.S.=Preciso, è una mia curiosità...

Dipende da cosa hai a disposizione. Se hai a disposizione strumenti sufficienti da poter ritenere valida una definizione per ricorsione, hai a disposizione l'operazione di concatenazione + e puoi confrontare le lunghezze delle stringhe, puoi definire una funzione del tipo
$\text{chomp} : (\Sigma^\star - \Sigma) \to \Sigma^\star$ tale che $\text{chomp}(s) = t$, dove $t$ è l'unica stringa per cui esiste una stringa $u$ di lunghezza 1: $t+u = s$ e una funzione $\text{last}: \Sigma^\star - {\epsilon} \to \Sigma$ tale che $\text{last}(s) = t$, dove t è l'unica stringa di lunghezza 1 per cui esiste $u in \Sigma^\star$ tale che $u+t=s$. A questo punto ti limiti a costruire la funzione successore $S$ per ricorsione, partendo dall'elemento 0 e da questi casi base:

$S(0) = 1$
$S(1) = 2$
$S(2) = 3$
.
.
.
$S(8) = 9$

Mentre per t != 0, 1, 2, 3, 4, 5, 6, 7, 8, $S(t) = $

$\text{- }last(t) != 9 => chomp(t)+S(last(t))$
$\text{- }last(t) = 9 => S(chomp(t))+0$

Ha senso, o ho sbarellato?

Puoi chiaramente anche costruire una relazione di equivalenza solita costruendo una funzione che "elimina" caratteri fino al primo non zero e dicendo che due stringhe sono equivalenti se e solo se le immagini secondo la funzione delle due stringhe sono uguali.

[garnak.olegovitc1]

Salve Odexios,

"Odexios":[Dipende da cosa hai a disposizione. Se hai a disposizione strumenti sufficienti da poter ritenere valida una definizione per ricorsione, hai a disposizione l'operazione di concatenazione + e puoi confrontare le lunghezze delle stringhe, puoi definire una funzione del tipo
$\text{chomp} : (\Sigma^\star - \Sigma) \to \Sigma^\star$ tale che $\text{chomp}(s) = t$, dove $t$ è l'unica stringa per cui esiste una stringa $u$ di lunghezza 1: $t+u = s$ e una funzione $\text{last}: \Sigma^\star - {\epsilon} \to \Sigma$ tale che $\text{last}(s) = t$, dove t è l'unica stringa di lunghezza 1 per cui esiste $u in \Sigma^\star$ tale che $u+t=s$. A questo punto ti limiti a costruire la funzione successore $S$ per ricorsione, partendo dall'elemento 0 e da questi casi base:

$S(0) = 1$
$S(1) = 2$
$S(2) = 3$
.
.
.
$S(8) = 9$

Mentre per t != 0, 1, 2, 3, 4, 5, 6, 7, 8, $S(t) = $

$\text{- }last(t) != 9 => chomp(t)+S(last(t))$
$\text{- }last(t) = 9 => S(chomp(t))+0$

Ha senso, o ho sbarellato?

Puoi chiaramente anche costruire una relazione di equivalenza solita costruendo una funzione che "elimina" caratteri fino al primo non zero e dicendo che due stringhe sono equivalenti se e solo se le immagini secondo la funzione delle due stringhe sono uguali.

ti ringrazio enormemente della risposa, premetto che non ho ancora ben capito la tua spiegazione in quanto non ho studiato teoria dei linguaggi formali e tutto ciò connesso, purtroppo sò solamente alcune def. e nient'altro ... ma farò uno sforzo di comprensione.....

Cordiali saluti

P.S.=Una curiosità, ma $\Sigma^**$ come lo definisci?

[Odexios]

"garnak.olegovitc":Salve Odexios,

[quote="Odexios"][Dipende da cosa hai a disposizione. Se hai a disposizione strumenti sufficienti da poter ritenere valida una definizione per ricorsione, hai a disposizione l'operazione di concatenazione + e puoi confrontare le lunghezze delle stringhe, puoi definire una funzione del tipo
$\text{chomp} : (\Sigma^\star - \Sigma) \to \Sigma^\star$ tale che $\text{chomp}(s) = t$, dove $t$ è l'unica stringa per cui esiste una stringa $u$ di lunghezza 1: $t+u = s$ e una funzione $\text{last}: \Sigma^\star - {\epsilon} \to \Sigma$ tale che $\text{last}(s) = t$, dove t è l'unica stringa di lunghezza 1 per cui esiste $u in \Sigma^\star$ tale che $u+t=s$. A questo punto ti limiti a costruire la funzione successore $S$ per ricorsione, partendo dall'elemento 0 e da questi casi base:

$S(0) = 1$
$S(1) = 2$
$S(2) = 3$
.
.
.
$S(8) = 9$

Mentre per t != 0, 1, 2, 3, 4, 5, 6, 7, 8, $S(t) = $

$\text{- }last(t) != 9 => chomp(t)+S(last(t))$
$\text{- }last(t) = 9 => S(chomp(t))+0$

Ha senso, o ho sbarellato?

Puoi chiaramente anche costruire una relazione di equivalenza solita costruendo una funzione che "elimina" caratteri fino al primo non zero e dicendo che due stringhe sono equivalenti se e solo se le immagini secondo la funzione delle due stringhe sono uguali.

ti ringrazio enormemente della risposa, premetto che non ho ancora ben capito la tua spiegazione in quanto non ho studiato teoria dei linguaggi formali e tutto ciò connesso, purtroppo sò solamente alcune def. e nient'altro ... ma farò uno sforzo di comprensione.....

Cordiali saluti

[/quote]Di niente! Se c'è qualcosa su cui può essere utile un chiarimento chiedi pure, può anche essere che ci siano punti sbagliati; non ho grosse basi in materia, se non qualche accenno su alfabeti, stringhe e operazioni fra stringhe.

P.S.=Una curiosità, ma $\Sigma^**$ come lo definisci?

Se $\Sigma$ è un alfabeto, cioè un insieme di caratteri, $s in \Sigma^\star iff (s = \epsilon vv s in \Sigma vv EE t in \Sigma^\star:\ EE u in \Sigma:\ t+u=s)$. Dovrebbe funzionare.

EDIT: Hm. Funziona per dire che $\Sigma^\star$ è una classe; per dimostrare che effettivamente è anche un insieme in questo momento non ho idee.

RIEDIT: Mi rendo conto di avere credo assunto implicitamente gli assiomi di ZF; in che contesto volevi lavorare? Ti interessa un discorso formale, o intuitivo? Cos'è esattamente che vuoi fare? Definire i numeri naturali prendendo gli assiomi soliti, ma trovando una costruzione alternativa a 0, S(0), S(S(0))?

Mi sono accorto di essere partito in quarta ma non aver effettivamente chiaro l'obiettivo xD

[garnak.olegovitc1]

Salve Odexios,

"Odexios":

RIEDIT: Mi rendo conto di avere credo assunto implicitamente gli assiomi di ZF; in che contesto volevi lavorare? Ti interessa un discorso formale, o intuitivo? Cos'è esattamente che vuoi fare? Definire i numeri naturali prendendo gli assiomi soliti, ma trovando una costruzione alternativa a 0, S(0), S(S(0))?

Mi sono accorto di essere partito in quarta ma non aver effettivamente chiaro l'obiettivo xD

aspetta un attimo, il tempo necessario e materiale di assimilare ciò scritto prima, non è un argomento dell'università quindi ci devo dedicare un pò di tempo.... a me sembra già formale di suò, non vorrei una cosa, invece, un pò troppo assiomatica. Ma intutivamente come sarebbe? Sai, per assimilare più in fretta... A meno che intuitivo per te era quello che hai scritto, se così fosse

Per quanto riguarda la costruzione dei $NN$ non saprei, conosco quella con assiomi di Peano, e quella con approccio insiemistico .... non sò se ne esiste un'altra solamente con il concetto di alfabeto e stringa e altro ancora .


Cordiali saluti