Hat der Begriff „Kontinuität“ in Mathematik und Informatik eine unterschiedliche Bedeutung?

Question

Ich stelle diese Frage aufgrund einiger Aussagen in der Frage „Was ist der Begriff ‚Kontinuität‘ in der berechenbaren Analyse?“ macht mich misstrauisch.

Ich bin Ingenieur und kein Informatiker, daher denke ich nicht an die Turing-Maschine, sondern an Logikgatter, wenn ich über algebraische Operationen nachdenke, die mit Geräten ausgeführt werden.

Ich habe die Antwort auf die Frage gelesen „Warum sind berechenbare Funktionen stetig?“ und habe es so verstanden:

Da die Eingabe des Geräts unendlich lang ist (eine Dezimalzahl mit unendlich vielen Nachkommastellen), kann das Gerät (z. B.Turingmaschine oder Computer) kann nicht die gesamte Zahl lesen, bevor sie geschrieben wird $n$-te Ziffer der Ausgabe.

Stattdessen kann das Gerät nur lesen $m(n)$ Ziffern der Eingabe beim Schreiben der $n$-te Ziffer der Ausgabe.

Wenn der erste $n$ Die Ziffern der Ausgabe einer Funktion hängen nur von der ersten ab $m(n)$ Je nach Ziffer der Eingabe ist die Funktion stetig.

Wenn ich diese Argumentation jedoch richtig verstehe, ist das Wort „kontinuierlich“ in der Berechnungstheorie nicht identisch mit dem Wort „kontinuierlich“ in der Mathematik:

Das Runden gegen Null würde nur das Lesen der Eingabe bis zum Dezimalpunkt erfordern (also $m(n)= ext{const.}$);Allerdings ist die berechnete mathematische Funktion gemäß der mathematischen Definition dieses Begriffs nicht „stetig“.

Wir könnten auch eine ziffernweise Operation durchführen ($m(n)=n$) und bestimmte Nachkommastellen austauschen;zum Beispiel alles ersetzen 4s vorbei 9s und alles 9s vorbei 4S.Soweit ich weiß, ist die berechnete Funktion in keinem Intervall von stetig $\mathbb{R}$ (Allerdings wäre es rechtskontinuierlich weiter $[0,\infty)$ und linkskontinuierlich weiter $(-\infty,0]$).

Und wenn ich keinen konzeptionellen Fehler gemacht hätte und wir a ausgewogenes Zahlensystem (wie ein Russischer Computer in den 1960er Jahren) anstelle des Dezimalsystems ein ähnlicher Algorithmus (Austausch 0s und 1s statt 4s und 9s) würde sogar eine mathematische Funktion darstellen, die ist nicht einmal richtungskontinuierlich in jedem Intervall von $\mathbb{R}$.

Fragen:

Hängt die Berechenbarkeit vom verwendeten Zahlensystem ab (wie das Beispiel mit dem ausgeglichenen Zahlensystem nahelegt) oder geht der Begriff „berechenbar“ überhaupt davon aus, dass ein bestimmtes Zahlensystem verwendet wird?

Ist die Beobachtung richtig, dass der Begriff „kontinuierlich“ in Mathematik und Informatik nicht die gleiche Bedeutung hat?

Answer 1

Wenn wir die Dezimalentwicklung zur Darstellung reeller Zahlen verwenden würden, würde Ihre Argumentation funktionieren.Aber das gibt uns eine sehr schlechte Vorstellung von Berechenbarkeit:

Vorschlag:Die Multiplikation mit 3 ist relativ zur Dezimaldarstellung nicht berechenbar.

Nachweisen:Angenommen, die Eingabe beginnt bei 0,3333333...Irgendwann muss unsere Berechnung anfangen, etwas auszugeben.Die beste Auswahl ist 0.und 1..Im ersten Fall haben wir es vermasselt, wenn unsere Eingabe als nächste Ziffer eine 4 enthält, auf die wir nicht geachtet haben;im zweiten Fall liegt eine 2 falsch.Daher können wir kein garantiertes Präfix der Lösung ausgeben.

Die Verwendung einer anderen Basis würde zu einer anderen Vorstellung von Berechenbarkeit führen, aber keine davon ist geeignet.Einige Möglichkeiten, die alle die gleiche gute Vorstellung von Berechenbarkeit liefern, sind:

1. Code ein echtes $x$ als Folge von Rationalsätzen $(q_n)_{n \in \mathbb{N}}$ so dass $ | x - q_n | <2^{-n} $.
2. Codieren Sie eine reelle Zahl über eine vorzeichenbehaftete Zifferndarstellung mit $\{-1,0,1\}$.
3. Code ein echtes $x$ als Folge rationaler Intervalle $(I_n)_{n \in \mathbb{N}}$ mit $\bigcap_{n \in \mathbb{N}} I_n = \{x\}$

Wenn wir von der Berechenbarkeit einer Funktion auf den reellen Zahlen sprechen, ohne anzugeben, welche Art von Darstellung wir verwenden, meinen wir eine davon (oder eine andere äquivalente).Das ist so, als ob wir nicht immer darauf hinweisen, die euklidische Topologie auf die reellen Zahlen anzuwenden. Wenn wir das tun, ist das nur der Standardfall.Wir können nun feststellen:

Satz:Die Funktionen auf den reellen Zahlen, die relativ zu einem Orakel berechenbar sind (im Sinne der Standarddarstellung), sind genau die stetigen Funktionen (im Sinne der euklidischen Topologie).

Um auf das Runden zurückzukommen: Dies zeigt, dass eine vollkommen exakte Rundung nicht funktionieren kann.Wir können dies jedoch umgehen, indem wir uns nicht auf Funktionen beschränken.Beispielsweise ist die folgende Aufgabe berechenbar:

Gegeben sei eine reelle Zahl $x \in [0,1]$, entweder ausgeben $0$ oder $1$.Wenn $x < 0,501$, Dann $0$ ist eine akzeptable Lösung und wenn $x > 0,499$, Dann $1$ ist eine akzeptable Lösung.

Wenn die Eingabe für die obige Aufgabe von stammt $[0.499,0.501]$, dann hängt die Antwort, die wir erhalten, nicht nur von der realen Realität ab, die wir betrachten, sondern auch von dem speziellen Code für diese reale Realität, den unser Algorithmus liest.Das kann das Nachdenken über Algorithmen etwas umständlicher machen, aber das können wir wirklich nicht vermeiden.