Qual è la "continuità" come termine nell'analisi calcolabile?

Question

Sfondo

La volta ho implementato un tipo di dati che rappresentano numeri reali arbitrari in Haskell. Etichetta ogni numero reale avendo una sequenza di cauchy convergendo ad esso. Ciò consentirà $ \ mathbb {r} $ essere nella solita topologia. Ho anche implementato l'aggiunta, la sottrazione, la moltiplicazione e la divisione.

Ma il mio insegnante ha detto: "Questo non sembra essere una buona idea. Dal momento che il confronto è indecidabile qui, questo non sembra molto pratico. In particolare, lasciando che la divisione da 0 per cadere in un loop infinito no Guarda bene. "

Così volevo che il mio tipo di dati prolungarsi $ \ mathbb {q} $ . Dal momento che il confronto della parità di $ \ mathbb {q} $ è decidabile, $ \ mathbb {q} $ è in topologia discreta. Ciò significa una topologia su $ \ mathbb {r} $ deve essere più fine della topologia discreta su $ \ mathbb {q} $ .

Ma, penso di averlo trovato, anche se potessi implementare un tipo di dati, sarà poco pratico.

Prova, passaggio 1

Let $ \ MATHBB {R} $ ESSERE PIÙ FINER DI $ \ MATHBB {Q} $ IN Topologia discreta. Quindi $ \ {0 \} $ è aperto in $ \ mathbb {r} $ . Assumere $ +: \ mathbb {r} ^ 2 → \ mathbb {r} $ è continuo. Quindi $ \ {(x, -x): x \ in \ mathbb {r} \} $ è aperto in $ \ mathbb {r} ^ 2 $ . Dal momento che $ \ mathbb {r} ^ 2 $ è nella topologia del prodotto, $ \ {(x, -x) \} $ è un elemento base di $ \ mathbb {r} ^ 2 $ per ogni $ x \ in \ mathbb {r} $ . Ne consegue che $ \ {x \} $ è un elemento base di $ \ mathbb {r} $ Per ogni $ x \ in \ mathbb {r} $ . Cioè, $ \ mathbb {r} $ è in topologia discreta.

Prova, passaggio 2

poiché $ \ mathbb {r} $ è in topologia discreta, $ \ mathbb {r} $ è comparevole l'uguaglianza comparibile. Questa è una contraddizione, quindi $ + $ non è continuo, e quindi non computabile .

domanda

Che cosa mi infastidisce è il testo in grassetto. È noto che ogni funzione calcolabile è continua (Weihrauch 2000, p.6). Anche se la definizione analitica e la definizione topologica della continuità coincidono in funzioni da e agli spazi euclidee, $-\ mathbb {r} $ sopra non è uno spazio euclideo. Quindi non sono sicuro se la mia prova è corretta. Qual è la definizione di "continuità" in analisi calcolabile?

Answer 1

Le persone diverse hanno opinioni diverse su ciò che dovrebbe essere la definizione di continuità, ma il modo in cui lo vedo, dovremmo definire la continuità per essere la calcuzzo relativa ad alcuni Oracle. Ad esempio:

Definizione : una funzione $ f: \ mathbf {x} \ to \ mathbf {y} $ è continuo, se c'è una funzione parziale calcolabile $ f: \ subeteq \ mathbf {x} \ volte \ mathbbs {n} ^ \ mathbbs {n} \ at \ mathbf {y} $ e Alcune $ p \ in \ mathbb {n} ^ \ mathbb {n} $ in modo tale che $ f (x)= f (x, p) $ .

Così il concetto più primitivo nella gestione di uno spazio è quale rappresentazione stiamo usando per questo, che poi produce la nozione di calcolo, e da ciò otteniamo la nozione di continuità.

Finora, la definizione di continuità sembra piuttosto estranea alla continuità dalla topologia, e si può chiedersi perché quel termine è stato scelto. Una ragione è che usiamo di solito rappresentazioni ammissibili , che hanno la caratterizzazione che le funzioni tra loro che sono continue nella definizione di analisi calcolabile sono esattamente le funzioni che sono continue nel senso topologico.

Se abbiamo una rappresentazione ammissibile $ \ delta: \ Somessoteq \ sigma ^ \ mathbb {n} \ a \ mathbf {x} $ , otteniamo la topologia su $ \ mathbf {x} $ come topologia finale lungo $ \ delta $ , ovvero un set < Span Class="Math-Container"> $ U \ SOCSETETQ \ MATHBF {X} $ è aperto se c'è un set $ W $ di parole finite tale che $ \ delta ^ {- 1} (u)=operatorname {dom} (\ delta) \ cap \ bigcup_ {w \ in w} w \ sigma ^ \ mathbbs { N} $ . Matthias Schröder ha dimostrato che gli spazi topologici che hanno rappresentazioni ammissibili sono esattamente la $ T_0 $ Quotanti di spazi basati su base.

Ora per tornare lentamente al punto di partenza della tua domanda, ciò che ci impedisce di utilizzare la topologia discreta sui reali? La ragione per cui non possiamo fare è che ogni spazio basato su base è separabile, cioè ha una sequenza densa (numerabile). Prendendo quotidianamente le preservazioni di essere separabili, quindi ogni topologia associata a una rappresentazione è necessariamente separabile. Uno spazio discreto è separabile IFF è numerabile, quindi non possiamo ottenere la topologia discreta sui reali.

C'è un modo per ottenere una rappresentazione ammissibile di $ \ mathbb {r} $ rende $ \ mathbb { Q} $ un sottospazio discreto (essenzialmente, trattare $ \ mathbb {r} $ come $ \ mathbb { N} ^ {*}} tazza \ mathbb {n} ^ \ mathbb {n} $ ), ma come si ha discusso nella domanda, che rende l'aggiunta non computabile (e nel complesso, ha pochissimo somiglianza con i veri Come vorremmo li vorremmo).

Su una nota laterale, che non possiamo evitare di rimanere bloccato senza nemmeno riconoscerlo quando cerca accidentalmente di dividere da $ 0 $ è un ostacolo significativo se stiamo cercando di fare Algebra lineare con numeri reali.

Riferimenti :

Pieter Collins: Analisi calcolabile con applicazioni a sistemi dinamici . Matematica. Struttura. Computer. SCI. 30 (2): 173-233 (2020)

Martín Hötzel Escardó: Topologia sintetica: di tipi di dati e spazi classici . Elettrone. Note teor. Computer. SCI. 87: 21-156 (2004)

Takayuki Kihara, Arno Pauly: Dividere per zero - Quanto è male, davvero? . MFCS 2016: 58: 1-58: 14

ARNO Pauly: sugli aspetti topologici della teoria degli spazi rappresentati . Computability 5 (2): 159-180 (2016) Arxiv

Matthias Schröder: ammissibilità estesa . THOROR. Computer. SCI. 284 (2): 519-538 (2002)

Answer 2

La risposta di Arno fornisce un materiale di lettura di sfondo molto utile, vorrei solo affrontare la tua domanda specifica su $ \ mathbb {r} $ .

Lascia che richiamiamo un risultato di Peter Hertling, vedi teorema 4.1 in Una struttura del numero reale che è efficacemente categorico ( pdf qui), sulla struttura computabile del numeri reali. Supponiamo di avere una rappresentazione di $ \ mathbb {r} $ , I.e., una struttura dati che rappresenta i reali, in modo che:

.
• $ 0 $ e $ 1 $ sono elementi calcolabili di $ \ mathbb {r} $ ,
• Le operazioni sul campo $ + $ , $ - $ , $ \ Times $ e $ / $ sono calcoli (dove la divisione per zero è ovviamente indefinita)
• L'operatore limite, prendendo una rapida sequenza di cauchy al limite, è calcolabile (una sequenza $ (x_n) _N $ è rapido quando $ | x_n - x_m | \ leq 2 ^ {- \ min (m, n)} $ ).
• l'ordine rigoroso $ < $ è semidecidable

Le condizioni di cui sopra indicano semplicemente che i Reali dovrebbero essere un campo ordinato Cauchy Computable, che è praticamente la versione calcolabile della solita cristallizzazione dei reali (l'assioma archimedea tiene pure, come risulta).

Allora ne consegue che:

.
1. La topologia della $ \ mathbb {r} $ è la topologia euclidea standard
2. L'uguaglianza è indecidabile, o equivalente, il test per zero è indecidabile.
3. Qualsiasi due tali strutture sono calcolabilmente isomorfiche.

Questi sono fatti inevitabili. Il tuo insegnante potrebbe pensare che non avesse un'uguaglianza decidabile è sfortunata, o quella divisione per zero dovrebbe segnalare un errore, ma impossibile disporre se si vuole mantenere la struttura calcolabile dei reali. Per quanto riguarda la tua implementazione: è vitale che tu rappresenti un reale con una sequenza di cauchy insieme a informazioni su quanto velocemente converge. Spero tu lo abbia fatto.