Insieme non R.E.

Calcolabilità, modelli di calcolo, complessità, linguaggi formali.

Insieme non R.E.

Messaggioda otacon7b il dom 14 dic 2008, 13:13

devo dimostrare che l'insieme S:\{x|\;\varphi_{x}\:\grave{e}\: totale\} non è ricorsivamente enumerabile. So dimostrarlo per assurdo però ho sentito che esiste anche una dimostrazione che sfrutta la diagonalizzazione, qualcuno di voi la conosce?
Avatar utente
otacon7b
 
Messaggi: 11
Iscritto il: gio 12 giu 2008, 20:21

Re: Insieme non R.E.

Messaggioda Nihilus il dom 26 gen 2014, 14:04

Sia $\mathcal R := \{ f: \mathbb N \rightarrow \mathbb N \, | \, f $ è ricorsiva $\}$ e sia $\gamma : \mathcal R \rightarrow \mathbb N$ un'iniezione (che esiste perché $\mathcal R$ è numerabile).
Supponiamo per assurdo che esista un'enumerazione ricorsiva dei codici di $\mathcal R$, essa induce un'enumerazione $\{ f_n\}_{n \in \mathbb N}$ di $\mathcal R$. Definiamo $g(n) := f_n(n)+1$ che è ricorsiva, ma non appartiene all'enumerazione.
Ultima modifica di Nihilus il mar 20 gen 2015, 20:11, modificato 1 volta in totale.
Cadi e non c'è nulla cui aggrapparti; cadi e la libertà è non trattenersi. Che perfezione...
Avatar utente
Nihilus
 
Messaggi: 102
Iscritto il: sab 22 set 2012, 14:05

Messaggioda salvo.tringali il dom 26 gen 2014, 15:53

otacon7b ha scritto:devo dimostrare che l'insieme S:\{x|\;\varphi_{x}\:\grave{e}\: totale\} non è ricorsivamente enumerabile.

Qualcuno mi spiega cosa vuol dire? Tanto per alleviare il peso della mia ignoranza. In particolare, cos'è $\varphi_x$ in questo contesto? Non riesco a interpretare la domanda.
"Che bella storia", disse l'Alchimista. | Whatever can be encoded by syntax shouldn't be left to semantics. | Homomorphisms are to algebraic structures as seminorms are to ordered structures.
Avatar utente
salvo.tringali
 
Messaggi: 5354
Iscritto il: mar 17 giu 2008, 19:46
Località: Karl-Franzens-Universität, Graz (AT)

Re: Insieme non R.E.

Messaggioda Nihilus il dom 26 gen 2014, 23:05

Di sicuro l'autore del post avrebbe potuto dispensare un po' più di chiarezza nel formulare la domanda. Mi sembra sensato interpretare quell'insieme un po' fumoso come $S = \{ x \in \mathbb N \, | \, \phi_x : \mathbb N \rightarrow \mathbb N$ è totale (e ricorsiva)$ \}$, dove il pedice è l'indice di enumerazione rispetto ad una fissata codifica aritmetica dell'insieme delle funzioni ricorsive. Correggetemi se sbaglio.
Cadi e non c'è nulla cui aggrapparti; cadi e la libertà è non trattenersi. Che perfezione...
Avatar utente
Nihilus
 
Messaggi: 102
Iscritto il: sab 22 set 2012, 14:05


Torna a Fondamenti dell'Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron