Il termine "continuità" ha un significato diverso in matematica e in informatica?

Question

Faccio questa domanda a causa di alcune affermazioni nella domanda "Qual è la 'continuità' come termine nell'analisi computabile?" rendendomi sospettoso.

Sono un ingegnere, non un informatico, quindi non ho in mente la macchina di Turing ma porte logiche quando penso alle operazioni algebriche eseguite con i dispositivi.

Ho letto la risposta alla domanda "Perché le funzioni calcolabili sono continue?" e inteso nel modo seguente:

Poiché l'input del dispositivo è di lunghezza infinita (un numero decimale con un numero infinito di cifre dopo il punto decimale), il dispositivo (es. Macchina di Turing o computer) non può leggere l'intero numero prima di scrivere il $n$-esima cifra di output.

Invece, il dispositivo può solo leggere $m(n)$ cifre dell'input quando scrive il file $n$-esima cifra di output.

Se il primo $n$ le cifre dell'output di qualche funzione dipendono solo dalla prima $m(n)$ cifre dell'ingresso, la funzione è continua.

Tuttavia, se comprendo correttamente questa argomentazione, la parola "continuo" nella teoria dei calcoli non è identica alla parola "continuo" in matematica:

L'arrotondamento verso lo zero richiederebbe solo la lettura dell'input fino al punto decimale (quindi $m(n)=\text{const.}$); tuttavia, la funzione matematica calcolata non è "continua" secondo la definizione matematica di quel termine.

Potremmo anche eseguire un'operazione in termini di cifre ($m(n)=n$) e scambiare alcune cifre dopo il punto decimale; per esempio sostituire tutti 4i 9s con se tutti i 9s con 4s. Per quanto ho capito, la funzione calcolata non è continua su qualsiasi intervallo di$\mathbb{R}$ (tuttavia, sarebbe diritto continuo su $[0,\infty)$ e continua a sinistra $(-\infty,0]$).

E se non avessi commesso un errore concettuale e usassimo un sistema numerico bilanciato (come un computer russo negli anni '60 ) invece del sistema decimale, un algoritmo simile (scambiando 0s e 1s invece di 4s e 9s) rappresenterebbe anche un funzione matematica che non è nemmeno direzionale continua su qualsiasi intervallo di$\mathbb{R}$.

Domande:

La computabilità dipende dal sistema numerico utilizzato (come suggerisce l'esempio con il sistema numerico bilanciato) o il termine "calcolabile" è anche ipotizzando che venga utilizzato un certo sistema numerico?

È corretta l'osservazione che il termine "continuo" non ha lo stesso significato in matematica e informatica?

Answer 1

Se dovessimo usare l'espansione decimale per rappresentare i numeri reali, il tuo ragionamento funzionerebbe. Ma questo ci dà una nozione di computabilità mal gestita:

Proposizione : la moltiplicazione per 3 non è calcolabile rispetto alla rappresentazione decimale.

Dimostrazione : supponiamo che l'input inizi con 0,3333333 ... Ad un certo punto, il nostro calcolo deve iniziare a produrre qualcosa. Le scelte migliori sono 0. e 1 .. Nel primo caso, abbiamo sbagliato se il nostro input ha un 4 come cifra successiva che non avevamo considerato; nel secondo caso un 2 ci fa sbagliare. Pertanto, non possiamo produrre un prefisso garantito della soluzione.

L'uso di una base diversa produrrebbe una diversa nozione di computabilità, ma nessuna di esse è adatta. Alcuni modi in cui tutti danno la stessa buona nozione di computabilità sono:

1. Codice un vero $x$ come una sequenza di razionali $(q_n)_{n \in \mathbb{N}}$ tale che $|x - q_n| < 2^{-n}$.
2. Codificare un reale tramite una rappresentazione di cifre con segno, utilizzando $\{-1,0,1\}$.
3. Codice un vero $x$ come una sequenza di intervalli razionali $(I_n)_{n \in \mathbb{N}}$ con $\bigcap_{n \in \mathbb{N}} I_n = \{x\}$

Quando parliamo di computabilità di una funzione sui reali senza specificare che tipo di rappresentazione stiamo usando, intendiamo una di queste (o un'altra equivalente). Questo è proprio come non indichiamo sempre usando la topologia euclidea sui reali, se lo facciamo, questo è solo il caso standard. Possiamo ora affermare:

Teorema : Le funzioni sui reali che sono calcolabili (rispetto alla rappresentazione standard) relative a qualche oracolo sono esattamente le funzioni continue (rispetto alla topologia euclidea).

Tornando all'arrotondamento, questo mostra che l'arrotondamento perfettamente esatto non può funzionare. Tuttavia, possiamo aggirare questo problema non limitandoci alle funzioni. Ad esempio, è calcolabile la seguente attività:

Dato un numero reale $x \in [0,1]$, output neanche $0$ o $1$. Se$x < 0.501$, poi $0$ è una soluzione accettabile e se $x > 0.499$, poi $1$ è una soluzione accettabile.

Se l'input per l'attività precedente proviene da $[0.499,0.501]$, quindi la risposta che otteniamo non dipende solo dal reale che stiamo guardando, ma dal codice particolare per quel reale che il nostro algoritmo legge. Ciò può rendere il ragionamento sugli algoritmi leggermente più complicato, ma non possiamo davvero evitarlo.