Die Mathe-Redaktion - 19.01.2018 12:22 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktZur Award-Abstimmung
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 690 Gäste und 19 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Mathematik » Logik, Mengen & Beweistechnik » Berechenbarkeit
Druckversion
Druckversion
Autor
Universität/Hochschule J Berechenbarkeit
Ehemaliges_Mitglied
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-01-03 19:25

\(\begingroup\)
Gestern und heute habe ich über diese Fragen nachgedacht, und will es hier im Forum teilen:

1) Es gibt Definitionen, die einem sagen, wann eine Funktion $f:\mathbb N\to \mathbb N$ berechenbar ist. Dieses Konzept der Berechenbarkeit von Funktionen $\mathbb N\to\mathbb N$ lässt sich wie folgt auf Funktionen $\mathbb N^n\to\mathbb N$ verallgemeinern: Es sei $\pi:\mathbb N^2\to\mathbb N$ die Cantorsche Paarungsfunktion und $\pi^{-1}:\mathbb N\to\mathbb N^2$ die inverse Funktion. Eine Funktion $f : \mathbb N^2\to\mathbb N$ heißt nun berechenbar, falls $f\circ \pi^{-1}$ berechenbar ist. Auf ähnliche Weise lässt sich induktiv die Berechenbarkeit von Funktionen $\mathbb N^n\to\mathbb N$ für jedes andere $n$ definieren, indem man Tupel $(x_1, x_2, \dots, x_n)$ als geschachtelte Tupel $(x_1, (x_2, \dots, x_n))$ betrachtet.

Wenn man statt $\pi$ irgendeine andere Bijektion $\mathbb N^2\to\mathbb N$ nehmen würde, würde man dann dasselbe Konzept der Berechenbarkeit von Funktionen $\mathbb N^n\to\mathbb N$ erhalten (d. h., wären die beiden Konzepte äquivalent)? Falls nicht, dann würde ich mich wundern: Welche Funktionen $J:\mathbb N^2\to\mathbb N$ darf man dann überhaupt statt $\pi$ benutzen, um die Berechenbarkeit von mehrstelligen Funktionen zu definieren? Sollte dann vorausgesetzt werden, dass $J$ selbst berechenbar ist ($\pi$ ist ja berechenbar)? Aber das wäre doch zirkulär (weil man ja gerade erst die Berechenbarkeit von mehrstelligen Funktionen definiert), oder?

2) Eine ähnliche Frage bezüglich des Halteproblems: In seiner Vorlesung spricht Ingo Blechschmidt davon, dass man die Turingmaschinen durchnummeriert, das heißt, er hat eine Bijektion $\psi:\mathbb N\to\{\text{Turingmaschinen}\}$ fixiert. Die Aussage, dass das Halteproblem nicht lösbar ist, ist dann folgende: Die Funktion $\mathbb N\to\mathbb N:n\mapsto \text{Wahrheitswert der Aussage, dass }\psi(n)\text{ hält}$ ist nicht berechenbar. Gilt das, egal welche Bijektion $\psi:\mathbb N\to\{\text{Turingmaschinen}\}$ man nimmt?

Ich glaube, die Antworten sind wie folgt:

1) Man muss fordern, dass $\pi$ (oder, äquivalent: $\pi^{-1}$) intuitiv berechenbar ist.

2) Den Satz über die Unlösbarkeit des Halteproblems müsste man trotzdem beweisen können. Mir ist aber unklar, was bei einer schlechten Wahl der Bijektion $\psi$ evtl. schief laufen könnte bzw. was nicht geht.
\(\endgroup\)


Wahlurne Für Ehemaliges_Mitglied bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 3808
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-01-03 20:16

\(\begingroup\)
Hallo asdfusername,

was meinst du damit, dass die Konzepte äquivalent sind? Meinst du damit, dass dieselben Funktionen "berechenbar" sind, egal welche Bijektion man wählt?

Ohne es jetzt zuende gedacht zu haben, würde ich sagen, dass das nicht der Fall ist, da dann vermutlich jede Funktion \(f;\IN\rightarrow\IN\) berechenbar wäre.
\(\endgroup\)


Wahlurne Für StrgAltEntf bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Ehemaliges_Mitglied
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-01-03 20:21


2018-01-03 20:16 - StrgAltEntf in Beitrag No. 1 schreibt:
Hallo asdfusername,

was meinst du damit, dass die Konzepte äquivalent sind? Meinst du damit, dass dieselben Funktionen "berechenbar" sind, egal welche Bijektion man wählt?

Wenn ich dich richtig verstehe, ja. Ich meine, dass die Konzepte der Berechenbarkeit dann äquivalent sind.



Wahlurne Für Ehemaliges_Mitglied bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 45125
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-01-03 20:23

\(\begingroup\)
2018-01-03 19:25 - asdfusername im Themenstart schreibt:
... dass $\pi$ (oder, äquivalent: $\pi^{-1}$) intuitiv berechenbar ist.
Hi asdfusername,
ich glaube nicht, dass die Berechenbarkeit einer Funktion mit der Berechenbarkeit der inversen Funktion äquivalent ist. //EDIT: Ich ziehe diese Bedenken zurück.
Für die Komplexität ist es so, dass diese für eine Funktion und die inverse Funktion nicht dieselbe ist.
Gruß Buri
\(\endgroup\)


Wahlurne Für Buri bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Ehemaliges_Mitglied
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2018-01-03 20:41

\(\begingroup\)
@Buri: Komplexität ist nicht Berechenbarkeit. Sei $f:A\to B$ bijektiv und berechenbar. Die Umkehrfunktion ist dann berechenbar. Algorithmus für die Umkehrfunktion: Nimm $b\in B$ als Eingabe. Gehe gehe der Reihe nach die Elemente $a\in A$ durch. Falls $f(a)=b$, dann stoppe und gebe $a$ aus.
EDIT: Der Algorithmus hält zu jeder Eingabe, da $f$ surjektiv ist. Die Funktion, die der Algorithmus berechnet, ist gerade die Umkehrfunktion, da das gefundene $a\in A$ aufgrund der Injektivität von $f$ immer eindeutig ist.
$A$ sei eine Menge der Form $\mathbb N^n$.

Oder habe ich einen Denkfehler?
\(\endgroup\)


Wahlurne Für Ehemaliges_Mitglied bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 3808
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-01-03 22:36


2018-01-03 20:21 - asdfusername in Beitrag No. 2 schreibt:
Wenn ich dich richtig verstehe, ja. Ich meine, dass die Konzepte der Berechenbarkeit dann äquivalent sind.

Ich verstehe nicht, was du mit Konzepten der Berechenbarkeit meinst und was es heißen soll, äquivalent zu sein. Ist äquivalent für dich gleich?



Wahlurne Für StrgAltEntf bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Ehemaliges_Mitglied
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2018-01-03 23:05

\(\begingroup\)
Ein Konzept der Berechenbarkeit von Funktionen $\mathbb N\to\mathbb N$ ist eine Definition, die uns sagt, wann eine Funktion $\mathbb N\to\mathbb N$ berechenbar ist, und wann nicht. Zwei solche Konzepte sind äquivalent, falls diese Definition äquivalent sind, d. h., wenn sie darin übereinstimmen, wann eine Funktion $\mathbb N\to\mathbb N$ berechenbar ist, d. h., wenn für alle Funktionen $f:\mathbb N\to\mathbb N$ gilt: $f$ ist genau dann nach der einen Definition berechenbar, wenn sie nach der anderen Definition berechenbar ist.
\(\endgroup\)


Wahlurne Für Ehemaliges_Mitglied bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
IngoBlechschmidt
Junior Letzter Besuch: im letzten Monat
Dabei seit: 09.11.2016
Mitteilungen: 13
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-01-03 23:10


2018-01-03 20:41 - asdfusername in Beitrag No. 4 schreibt:
Oder habe ich einen Denkfehler?

Nein, das passt so! Ich teile deine Antwort bezüglich 1) (aus deinem ersten Posting in dieser Diskussion).

Bezüglich 2): Nein, wenn man andere Bijektionen nimmt, wird die Aussage hart falsch. In einer klassischen Metalogik kannst du etwa eine Bijektion konstruieren, die allen haltenden Turingmaschinen gerade Indizes gibt und allen anderen ungerade. Mit dieser Kodierung wird das Halteproblem trivial lösbar.

Ein Kriterium, mit dem du festmachen kannst, ob du eine sinnvolle Bijektion gewählt hast, ist, dass die universelle Turingmaschine (welche einen Index für eine Turingmaschine und eine Zahl als Argumente nimmt und die so beschriebene Maschine mit dem Argument simuliert) implementierbar ist.

[Die Antwort wurde nach Beitrag No.4 begonnen.]



Wahlurne Für IngoBlechschmidt bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 3808
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2018-01-04 00:19

\(\begingroup\)
2018-01-03 23:05 - asdfusername in Beitrag No. 6 schreibt:
$f$ ist genau dann nach der einen Definition berechenbar, wenn sie nach der anderen Definition berechenbar ist.

Sag ich doch ... wieso drückst du das also so merkwürdig aus?  wink
\(\endgroup\)


Wahlurne Für StrgAltEntf bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Ehemaliges_Mitglied
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2018-01-04 07:25


Vielen Dank, Ingo!



Wahlurne Für Ehemaliges_Mitglied bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 125
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2018-01-04 23:59


2018-01-03 23:10 - IngoBlechschmidt in Beitrag No. 7 schreibt:
Nein, das passt so! Ich teile deine Antwort bezüglich 1) (aus deinem ersten Posting in dieser Diskussion).

Ich denke, daß das so nicht stimmt. Es geht ja um folgendes: Wenn man einen Berechenbarkeitsbegriff für 1-stellige Funktionen hat, wie erweitert man diesen auf k-stellige Funktionen? Wie in #1 geschrieben kann man das mit der (verallgemeinerten) Paar-Funktionen machen, einer Gödelisierung von fed-Code einblenden . Man kann jede andere Gödelisierung wählen, aber die "Bijektion" muß berechenbar sein ("intuitiv" berechenbar wie in #1 vermutet ist zu schwach).

2018-01-03 23:10 - IngoBlechschmidt in Beitrag No. 7 schreibt:
Bezüglich 2): Nein, wenn man andere Bijektionen nimmt, wird die Aussage hart falsch. In einer klassischen Metalogik kannst du etwa eine Bijektion konstruieren, die allen haltenden Turingmaschinen gerade Indizes gibt und allen anderen ungerade. Mit dieser Kodierung wird das Halteproblem trivial lösbar.

Das klappt nur, weil die so konstruierte Bijektion nicht berechenbar ist. Das Beispiel mit den Turingmaschinen funktioniert mit der Forderung "berechenbar" nicht. Wegen der Bijektivität von Gödelisierungen ist der Berechenbarkeitsbegriff für k-stellige Funktionen unabhängig von der für fed-Code einblenden gewählten Gödelisierung .




Wahlurne Für Zwerg_Allwissend bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Ehemaliges_Mitglied hat die Antworten auf ihre/seine Frage gesehen.
Ehemaliges_Mitglied 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-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]