Beweis: Existenz einer nicht berechenbaren Funktion N->N |
| 05.11.2015, 17:58 | te one | Auf diesen Beitrag antworten » |
| Beweis: Existenz einer nicht berechenbaren Funktion N->N ich soll beweisen, dass es eine nicht berechenbare Funktion N -> N gibt. Hierbei wurde berechenbar so definiert, dass es einen Algorithmus gibt, der f(n) für jedes beliebige n e N ausrechnet. Ein Algorithmus ist hierbei ein Text endlicher Länge aus 0en und 1en. Durch Zwischenaufgaben habe ich bereits gezeigt, dass 1. die Menge aller Algorithmen gleichmächtig zu N ist 2. die Menge aller Funktionen N -> N mächtiger als N ist Nun wollte ich eigentlich sagen, dass weil die 2. Menge mächtiger als die 1. ist, es ja ein Element in 2. Menge geben muss, das nicht in 1. ist. Jedoch könnte ja theoretisch ein Element der Menge 1 zu mehreren der Menge 2 gehören!? Kann aber nicht sein... Wo steckt der Fehler? Wie argumentiere ich in diesem Fall korrekt? |
||
| 05.11.2015, 19:52 | URL | Auf diesen Beitrag antworten » |
| RE: Beweis: Existenz einer nicht berechenbaren Funktion N->N Zwei verschiedene Funktionen aus der Menge 2 unterscheiden sich an mindestens einer Stelle |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
