Sottoinsiemi ricorsivi di insiemi ricorsivamente enumerabili

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

Sottoinsiemi ricorsivi di insiemi ricorsivamente enumerabili

Messaggioda Nihilus il mar 20 gen 2015, 17:18

Voglio rivitalizzare un po' questa sezione polverosa e dimenticata.

Dimostrare che ogni insieme ricorsivamente enumerabile infinito contiene un insieme ricorsivo infinito.

Se non si riesce a cavare un ragno dal buco c'è un suggerimento.
Dimostrare preliminarmente che un insieme infinito $A \subseteq \mathbb N$ è ricorsivo sse è l'immagine di una funzione ricorsiva strettamente crescente.
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 fry il mar 20 gen 2015, 23:14

Nihilus ha scritto:Dimostrare che ogni insieme ricorsivamente enumerabile infinito contiene un insieme ricorsivo infinito.

Sia $S \subseteq \mathbb{N}$ un insieme ricorsivamente enumerabile infinito, quindi esiste una funzione ricorsiva $f : \mathbb{N} \to \mathbb{N}$ tale che $\operatorname{im}(f) =S$.Diciamo che $s \in S$ è un "picco" di $f$ se preso il minimo $n \in \mathbb{N}$ tale che $s = f(n)$ si ha che $f(m) < f(n)$, per ogni $m \in \mathbb{N}$, con $m < n$. Sia $S^\prime$ l'insieme dei picchi di $f$. Se per assurdo $S^\prime$ fosse finito, allora esisterebbe $n_0 \in \mathbb{N}$ tale che per ogni $n \in \mathbb{N}$ con $n > n_0$ risulta che $f(n)$ non è un picco di $f$, ovvero $f(n) \leq f(m)$ per qualche $m \in \mathbb{N}$ con $m < n$. Ne consegue che $f(n) \leq \max\{f(m) : m \in \mathbb{N}, \, m \leq n_0\}$ per ogni $n \in \mathbb{N}$, il che è assurdo, poiché $S$ è infinito. Dunque $S^\prime$ è infinito. Per la infinitezza di $S$, il seguente algoritmo termina sempre e stabilisce se un $k \in \mathbb{N}$ appartiene o no a $S^\prime$, quindi $S^\prime$ è ricorsivo.

$\text{input }k \in \mathbb{N}$
$n \leftarrow 0$
$\text{while } f(n) < k$
$\phantom{aaaa} n \leftarrow n + 1$
$\text{if } f(n) = k$
$\phantom{aaaa}\text{return "} k \in S^\prime \text{"}$
$\text{else}$
$\phantom{aaaa}\text{return "} k \notin S^\prime \text{"}$
"Hey. They laughed at Louis Armstrong when he said he was gonna go to the moon. Now he's up there, laughing at them."
Avatar utente
fry
 
Messaggi: 1122
Iscritto il: ven 20 giu 2008, 19:06

Re: Sottoinsiemi ricorsivi di insiemi ricorsivamente enumerabili

Messaggioda Nihilus il mer 21 gen 2015, 0:09

Perfetto!
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