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

Question

Chiedo questa domanda a causa di alcune affermazioni nella domanda " Qual è la "continuità" come termine in analisi calcolabile? " rendimi sospetto.

Sono ingegnere, non scienziato informatico, quindi non ho la macchina di Turing ma la logica in mente quando sto pensando alle operazioni algebriche eseguite con dispositivi.

Leggo la risposta alla domanda "Perché le funzioni calcolabili sono continue?" e lo ha capito nel modo seguente:

.

Poiché l'ingresso del dispositivo è di lunghezza infinita (un numero decimale con un numero infinito di cifre dopo il punto decimale), il dispositivo (ad es. Macchina o computer) non può leggere l'intero numero prima di scrivere la matematica $ N $ -th Digita di uscita.

Invece, il dispositivo può aver solo letto $ m (n) $ cifre dell'ingresso quando scrive la $ n $ -th digit di output.

Se il primo $ N $ cifre dell'output di qualche funzione dipende solo dalla prima classe $ m (n) $ cifre dell'input, la funzione è continua.

Tuttavia, se capisco correttamente questa argomentazione, la parola "continua" nella teoria del calcolo non è identica alla parola "continuo" in matematica:

L'arrotondamento verso zero richiederebbe solo leggere l'ingresso fino al punto decimale (SO $ M (N)=TESTO {CONST.} $ ); Tuttavia, la funzione matematica calcolata non è "continua" in base alla definizione matematica di quel termine.

Potremmo anche eseguire un'operazione di digit-saggio ( $ m (n)= n $ ) e scambia determinate cifre dopo il punto decimale; Ad esempio, sostituire tutti i 4s da 9s e tutti i 9s da 4s. Per quanto ho capito, la funzione che viene calcolata non è continua su qualsiasi intervallo di $ \ mathbb {r} $ (tuttavia, sarebbe giusto-continuo su $ [0, \ Infty) $ e sinistra-continuo su $ (- \ INFTY, 0] $ ).

E se non avessi un errore concettuale e usiamo un sistema numerico equilibrato (come un Computer russo negli anni '60 ) invece del sistema decimale, un algoritmo simile (scambiando Generacodictagcodes e 0s invece di 1s e 4s) rappresenterebbero persino una funzione matematica che è non nemmeno continue direzionale su qualsiasi intervallo di $ \ mathbb {r} $ < / span>.

Domande:

viene visualizzata la computabilità dipendente dal sistema numerico (come suggerisce l'esempio con il sistema numerico equilibrato) o è il termine "calcolo" anche assumendo un determinato sistema numerico utilizzato?

L'osservazione è corretta che il termine "continuo" non ha lo stesso significato in matematica e cs?

Answer 1

Se dovessimo usare l'espansione decimale per rappresentare numeri reali, il tuo ragionamento funzionerebbe. Ma questo ci dà una nozione di calcolo di calcolo molto grave:

Proposition : la moltiplicazione di 3 non è calcolabile rispetto alla rappresentazione decimale.

Prova : Assumi L'input inizia 0.33333333 ... ad un certo punto, il nostro calcolo deve iniziare a generare qualcosa. Le migliori scelte sono 0. e 1 .. Nel primo caso, ci siamo avvitati se il nostro input ha un 4 come la prossima cifra non avevamo esaminato; Nel secondo caso un 2 ci rende sbagliato. Pertanto, non possiamo emettere un prefisso garantito della soluzione.

L'utilizzo di una base diversa produrrebbe una diversa nozione di calcolo, ma nessuno di essi è adatto. Alcuni modi che tutti producono la stessa buona idea di calcolo sono:

.
1. Codice una vera $ x $ come sequenza di razionali $ (q_n) _ {n \ in \ mathbb { N}} $ in modo tale che $ | x - Q_n | <2 ^ {- n} $ .
2. Codice un reale tramite una rappresentazione di cifre firmata, utilizzando $ \ {- 1,01 \} $ .
3. Codice una vera $ x $ come 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 quale tipo di rappresentazione stiamo utilizzando, intendiamo uno di questi (o un altro equivalente). Questo è proprio come non farlo sempre sotto usando la topologia euclidea sui reali se lo facciamo, questo è solo il caso standard. Ora possiamo dichiarare:

Teorema : Le funzioni sui reali che sono calcolabili (Wrt la rappresentazione standard) relativa ad alcuni Oracle sono esattamente le funzioni continue (Wrt la topologia euclidea).

Tornando all'arrotondamento, questo dimostra che l'arrotondamento perfettamente esatto non può funzionare. Tuttavia, possiamo circonferendo questo non limitarci a funzioni. Ad esempio, la seguente attività è calcolabile:

Dato un numero reale $ x \ in [0,1] $ , output $ 0 $ < / span> o $ 1 $ . Se $ x <0,501 $ , quindi $ 0 $ è una soluzione accettabile e se la matematica $ x> 0,499 $ , quindi $ 1 $ è una soluzione accettabile.

Se l'ingresso all'attività sopra è da $ [0.499.0.501] $ , quindi la risposta che otteniamo non solo dipende dal reale che stiamo esaminando , ma sul codice particolare per quello reale che legge il nostro algoritmo. Ciò può rendere il ragionamento degli algoritmi leggermente più ingombranti, ma non possiamo davvero evitarlo.