Michael Putzmann

Was heißt 'algorithmische Form'? TURING-, Super-TURING- und Nicht-TURING-Berechenbarkeit und informationstheoretische Aspekte

Das Problem
'TURINGMaschine' und 'CHURCH-TURING-These' sind klassische Paradigmen der 'Berechenbarkeit' - ALAN TURINGs Präzisierung des intuitiven Algorithmenbegriffs [14] und die Annahme, dass jeder Algorithmus im präzisen Sinn ein Algorithmus im intuitiven Sinn ist, bzw. v.v., dass zu jedem Algorithmus im naiven Sinn ein äquivalenter im präzisen Sinn existiert, unterstellen den Begriff 'Information' einer Theorie rationaler (deduktiver und induktiver) Entscheidungen. Der erste GÖDELsche Unvollständigkeitssatz und eine Vielfalt von Unentscheidbarkeitsresultaten zeigen, dass es konkrete Fragestellungen gibt, die sich nicht algorithmisch lösen lassen. Dazu sind verschiedene 'nicht-klassische' BerechenbarkeitsModelle vorgeschlagen, die - ausgehend von TURINGs eigener Idee der 'OrakelMaschine' - mehr berechnen bzw. 'entscheiden' können, als die Modelle im orthodoxen TURINGParadigma. Im TURINGParadigma sind Berechnungen beschreibbar durch nachvollziehbare endliche Programme/Algorithmen, die rationalen Parametern korrespondieren. Jenseits der 'TURINGBarriere' liegen Berechnungen, die nicht mit endlichen Mitteln beschreibbar sind - Berechnungen ohne Programm. In der Beobachtung natürlicher Phänomene und ihrer 'erklärenden' Darstellung ist es nicht mehr der Algorithmus, der kommuniziert werden kann, sondern bestenfalls die 'Fähigkeit' zur Beobachtung eines (phänomenalen) Prozesses. Die Frage ist, wie die logische Struktur dieser 'Erfahrung' aussehen könnte, bzw. ob es  e i n e  solche Struktur/Form gibt. 

Motivation
(A) Zwischen den Konzepten der 'Berechenbarkeit' und der 'Information' besteht ein enger Zusammenhang. CHAITIN [2], KOLMOGOROFF [8] und SOLOMONOFF [3] entwickelten einen Informationsbegriff, der dem intuitiven Verständnis von 'Komplexität' entspricht: 'algorithmischer Informationsgehalt' mißt aktuelle Information unter syntaktischen und semantischen Aspekten und bedeutet ein subjektives bzw. relatives Maß. -                      

Halg (x) = L (pmin → x)                                                                         (1.1)
Sei x eine lange, evtl. unendliche Zeichenfolge, dann ist Halg (x) definiert als Länge L des kürzesten 'ComputerProgramms' oder 'Algorithmus' pmin, der es ermöglicht, x zu erzeugen. - 

Die algorithmische Informations- bzw. Komplexitätstheorie gilt 'relativ' unter Voraussetzung der Algorithmisierbarkeit (Berechenbarkeit) durch das Konzept der TURINGMaschine. Wie ändert sich der Begriff 'algorithmische Information' bzw. - Komplexität' relativ zu Nicht-TURINGModellen?

(B) 'Quasi-empirische' (LAKATOS [9]) Interpretation der Mathematik und ihrer epistemologischen Funktion, d.h. ihre pragmatische Rechtfertigung, erhebt die Frage nach möglichen Determinanten dieser Praxis.  Vielversprechend ist hier die Frage nach 'ästhetischen Prinzipien' von Information - vgl. LEYTONs two principles of aesthetics (1) maximizing transfer of structure und (2) maximizing recoverability of the generative operations -    

Transfer is formalized in terms of particular product of groups.  It is shown to be the basis of Gestalt.  Recoverability is shown to depend on a new theory of symmetry breaking, provided in the geometric theory. Together, transfer and recoverability are shown to be the basis of memory storage. [11]:289 -

Ausgezeichnet an dieser Auffassung ist der grundsätzliche Zusammenhang künstlersicher und wissenschaftlicher Epistemologie:

[...] Science achieves this by converting existing objects into maximal memory stores. Art achieves this by creating new objects as maximal memory stores. [ibid.]:310

Grundlagen
Zur Geschichte der Präzisierungsbemühungen des Algorithmenbegriffs s. z.B. [4]; Re-Evaluierung von Berechenbarkeitstheorien bzw. -Modellen s. HYPERCOMPUTATION RESEARCH NETWORK [15]; Literatur zur Epistemologie der Berechenbarkeit [5] bzw. wissenschaftsphilosophischen Problem von 'Struktur' s. z.B. d. Übers. i. [1, 6].

Methodologische Ansätze
Wesentlich für das Studium symbolischer Praktiken (piktorialer, verbaler u.a.) ist die Wahl einer geeigneten Beschreibungssprache. Neben QUINES Verfahren der 'Quasi-Anführung' [12] bieten kategorientheoretische Interpretationen abstrakter Struktureigenschaften die aussichtsreichten Möglichkeiten [10, 13]. Zugang zur Pragmatik eröffnet etwa GOODMANs 'Symboltheorie' [7] .

Schwierigkeiten
'Informale' Theorien bzw. Modelle können nicht (semi-)formal interpretiert werden. Hinzu kommt, dass Nicht-TURING-Konzepte unvereinbar sind mit gegenwärtig akzeptierten physikalischen und logischen Theorien, d.h. als nicht-realisierbar gelten. Es erhebt sich die Frage, inwieweit überhaupt 'rationale Standards' zu ihrer Hermeneutik genügen können.

Erwartete Ergebnisse
Die Möglichkeit nicht-intuitiver Berechenbarkeit bzw. Information muss nicht die Absage an 'Algorithmizität' bedeuten. Ein modifizierter Algorithmenbegriff, z.B. einer sprachlich-kommunikablen Beobachtungsfähigkeit der 'Phänomene' (KLEENE/HOFSTADTER), könnte die orthodoxe TURINGMaschine, wie auch ihre 'heterodoxen' Alternativen umfassen.  Kenntnis pragmatisch-konstruktivistischer Elemente, wie sie ästhetische Kriterien darstellen, ist wesentlicher Faktor für die Bestimmung dessen, was wir  'rechnerisch'  w i s s e n  können.

Ausblicke
Was besagt ein erweiterter Begriff von Algorithmizität, d.h. prinzipieller Berechenbarkeit bzw. Information für das bisher im TURINGParadigma als unangreifbar eingeschätzte "P = NP?"-Problem der Komplexitätstheorie?

Anm. Literatur
[1] BRADING, K., LANDRY, E., A minimal construal of scientific structuralism. In Proceedings Philosophy of Science Assoc. 19th Biennial Meeting - PSA2004: PSA 2004 Symposia, Austin, Texas. (Rev.2005) - [2]  CHAITIN, G.J., Algorithmic Information Theory, Cambridge UP, 1987 - [3]  ＿＿, From philosophy to program size, Lecture notes on algorithmic information theory, EWSCS'03, <http://www.cs.auckland.ac.nz/CDMTCS/chaitin/eesti.html#1> - [4] CROSSLEY, J.N., Reminiscences on logicians. In J.N. CROSSLEY (ed.) Algebra and Logic. Lecture Notes in Mathematics. Springer 1975, 1-62. - [5] EBBINGHAUS,  H.D., Maschinen und Kreativität: Metamathematische Argumente für das menschliche Denken. Philosophia naturalis 1992, 29:1-30. -  [6] FORGE, J. Reflections on Structuralism and Scientific Explanation. Phil.Sci. 2001, < philsci-archive.pitt.edu/archive/00000161/ > - [7] GOODMAN, N.; ELGIN, C. Z., Reconceptions in Philosophy and Other Arts and Sciences. London: Routledge 1988. - [8] KOLMOGOROFF, A. Three Approaches to the Quantitative Definition of Information. Problems. Information Transmission 1(1965), 1-7. - [9] LAKATOS, I., A renaissance of empiricism in the recent philosophy of mathematics? In TH. TYMOCZKO (ed.), New Directions in the Philosophy of Mathematics, Princeton UP, 1998, part I, 29-49. - [10] LANDRY, E., Category theory: the language of mathematics. Phil.Sci.(Proc.) (1999) S14-S27. - [11] LEYTON, M., The Foundation of Aesthetics, in: FISHWICK, P.A., Aesthetic Computing, Cambridge (MA): MIT Press (2006), 289-313. - [12] QUINE, W.V.O., Mathematical Logic, Revised Edition. Cambridge M 1951, XII+346. - [13] SEMADENI, Z.; WIWEGER, A., Einführung in die Theorie der Kategorien und Funktoren, Leipzig: B.G. Teubner, 1979. - [14] TURING, A.M., On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, 1936, Ser. 2-42, 230-265. - [15] <http://hypercomputation.net/index.html>

Zur Person

1993-2000 Diplom 'Interdisziplinäre Kunst/Medienkunst' Leipzig HGB (Academy of Visual Arts), 2001-2004 Meisterschüler Medienkunst HGB (Academy of Visual Arts), 2001-2007 Universität Leipzig Stud. M.A. Informatik, Logik, Wissenschaftstheorie, derzeit  KHM Köln Promotionsstudium bei Prof. Dr. Ing. Georg Trogemann