Matroids Matheplanet Forum Index
Moderiert von Bilbo
Informatik » Theoretische Informatik » Entscheidbarkeit von Zeit- und Platzkomplexität
Autor
Universität/Hochschule Entscheidbarkeit von Zeit- und Platzkomplexität
LarsOf
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 02.05.2021
Mitteilungen: 4
  Themenstart: 2021-07-03

Hallo zusammen! Ich hätte eine Frage zu der ich bis jetzt wenig Anhaltspunkte finden konnte. Und zwar geht es darum, ob entscheidbar ist, ob eine deterministische Turingmaschine eine bestimmte Zeit- oder Platzkomplexität besitzt. Mein erster Gedanke war, dass diese Eigenschaften semi-eintscheidbar sein müssten, da man ja für alle Eingaben den Zeit- oder Platzbedarf prüfen müsste und daher bei unendlich vielen Eingaben nicht terminieren würde. Aber das scheint mir doch zu simpel gedacht. Könnte man evtl. über den Satz von Rice argumentieren? Würde mich freuen falls mich hier jemand auf die richtige Spur bringen kann.


   Profil

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]