Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Irreversible Zahlen, eingeschränkte Berechenbarkeit
Druckversion
Druckversion
Autor
Kein bestimmter Bereich J Irreversible Zahlen, eingeschränkte Berechenbarkeit
Nunie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.12.2018
Mitteilungen: 33
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-07-22 09:15


Auf der Suche nach Methoden für ein besseres mathematisches Verständnis von Vorgängen die in der Quantenmechanik beobachtet wurden und weil es mir bei einem anderen Beweis nützlich sein könnte, wollte ich mal fragen, ob es n-mal berechenbare Zahlen gibt:

Eine Zahl n liegt in der Menge der n-mal berechenbaren Zahlen, wenn sie genau n-mal berechenbar ist.
(Das wäre sogar eine Äquivalenzrelation)
"Eine Funktion ist berechenbar, wenn für sie eine Berechnungsanweisung (Algorithmus) formuliert werden kann"(wiki).
Man kann eine Berechnungsanweisung für die Zahl n formulieren, deren Ausführung per Definition nur n-mal auf eine Lösung aus der Menge "n-mal berechenbar" zeigt.

Gibt es dieses Konstrukt in der Mathematik?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2027
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-07-22 09:27


Hallo Nunie,

ich verstehe leider überhaupt nicht, was Dein Anliegen ist.

Wie aus dem von Dir zitierten Satz aus Wikipedia hervorgeht, ist Berechenbarkeit eine Eigenschaft von Funktionen, nicht von Zahlen.

Wenn es eine Berechnungsvorschrift gibt, ist die Funktion berechenbar; wenn nicht, dann ist sie nicht berechenbar. Was "n-mal berechenbar" heißen soll, müsstest Du näher ausführen (aber wie gesagt, für Funktionen).


Viele Grüße
Thorsten


-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nunie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.12.2018
Mitteilungen: 33
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2021-07-22 09:41


Ja, Funktionen und Zahlen sollte man nicht zusammenwerfen. Sorry.
Dann bleiben wir bei Funktionen.

Mich würde interessieren, ob es sozusagen zerfallende Funktionen gibt, also ob man eine Berechnungsvorschrift so formulieren könnte, dass sie nach n-maliger Anwendung nicht mehr ausführbar wäre.

Vielleicht wäre die semi-berechenbare Menge das Gesuchte.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2027
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-07-22 10:27


Hallo Nunie,

das ist doch alles viel zu schwammig formuliert.

Was soll "n-malige Anwendung" heißen?

Meinst Du, ob es eine berechenbare Funktion <math>f:\mathbb{N}\to\mathbb{N}</math> gibt, für die <math>f^2=f \circ f</math> sowie <math>f^3=f \circ f \circ f</math>, ... berechenbar sind, aber <math>f^{n+1}</math> nicht mehr?

Wenn das die Frage ist, lautet die Antwort nein, denn Kompositionen berechenbarer Funktionen sind immer berechenbar.


Viele Grüße
Thorsten


[Verschoben aus Forum 'Logik, Mengen & Beweistechnik' in Forum 'Berechenbarkeitstheorie' von Bilbo]


-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nunie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.12.2018
Mitteilungen: 33
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2021-07-22 11:19


Hallo Thorsten,

Habe ich Semi-Berechenbarkeit richtig verstanden:
Solange nur ein Teil ( echt größer als Null ) einer Funktion in der Menge der Berechenbaren Funktionen liegt, ist diese Funktion semi-berechenbar?

Eine Komposition wäre ja eine Verknüpfung auf der Menge der Funktionen und kommt wie du in deiner Ausführungen gezeigt hast nicht in Frage.

Es müsste tatsächlich eine Verknüpfung sein für die erst
\(f^{n+1}\) nicht mehr berechenbar wäre.
Gibt es eine solche Art von Verknüpfung?

Man könnte doch einen Algorithmus formulieren, der zählt, wie oft er ausgeführt wurde und nach einer vordefinierten Anzahl an Ausführungen aufhört zu einem Ergebnis zu kommen, oder nicht?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2027
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2021-07-22 11:38


Hallo Nunie,

2021-07-22 11:19 - Nunie in Beitrag No. 4 schreibt:
Solange nur ein Teil ( echt größer als Null ) einer Funktion in der Menge der Berechenbaren Funktionen liegt, ist diese Funktion semi-berechenbar?

Auch das ist wieder eine Aussage, die keinen Sinn ergibt, solange Du nicht erklärst, was Du mit "Teil (echt größer als Null) einer Funktion" meinst.
Eine Funktion ist zum Beispiel die Funktion <math>f:\mathbb{N}\to\mathbb{N}, x\mapsto x^2</math>. Was wäre für Dich nun ein "Teil" dieser Funktion?


Man könnte doch einen Algorithmus formulieren, der zählt, wie oft er ausgeführt wurde und nach einer vordefinierten Anzahl an Ausführungen aufhört zu einem Ergebnis zu kommen, oder nicht?

Meinst Du einen Algorithmus, der nach einer bestimmten Anzahl von Schritten aufhört? Also präzise eine Turingmaschine, die nach einer bestimmten Schrittzahl stoppt?

Falls Du das meinst: So etwas wurde natürlich schon untersucht, das Stichwort lautet Zeitkomplexität.

Viele Grüße
Thorsten


-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nunie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.12.2018
Mitteilungen: 33
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2021-07-22 12:29


2021-07-22 11:38 - Bilbo in Beitrag No. 5 schreibt:
Hallo Nunie,

2021-07-22 11:19 - Nunie in Beitrag No. 4 schreibt:
Solange nur ein Teil ( echt größer als Null ) einer Funktion in der Menge der Berechenbaren Funktionen liegt, ist diese Funktion semi-berechenbar?

Auch das ist wieder eine Aussage, die keinen Sinn ergibt, solange Du nicht erklärst, was Du mit "Teil (echt größer als Null) einer Funktion" meinst.
Eine Funktion ist zum Beispiel die Funktion <math>f:\mathbb{N}\to\mathbb{N}, x\mapsto x^2</math>. Was wäre für Dich nun ein "Teil" dieser Funktion?

"Anschaulich gesprochen berechnet f also für je zwei natürliche Zahlen diejenige, die eher in A liegt. Das bedeutet, sobald mindestens einer der beiden Eingaben tatsächlich in A liegt, wird auch ein Element von A zurückgegeben."von hier hier

Zeitkomplexität scheint das Richtige zu sein.
Vielen Dank



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nunie hat die Antworten auf ihre/seine Frage gesehen.
Nunie hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]