Undecidability and Algorithmic Intractability in Social Sciences

• Authors: Witold Marciszewski

Title variants

PL

Nierozstrzygalność i algorytmiczna niedostępność w naukach społecznych

EN

Undecidability and Algorithmic Intractability in Social Sciences

• Languages of publication: PL

Abstracts

PL

The paper is meant as a survey of issues in computational complexity from the standpoint of its relevance to social research. Moreover, the threads are hinted at that lead to computer science from mathematical logic and from philosophical questions about the limits and the power both of mathematics and the human mind. Especially, the paper addresses Turing's idea of oracle, considering its impact on computational (i.e., relying on simulations) economy, sociology etc. Oracle is meant as a device capable of finding the values of uncomputable functions. Such an idealized entity is exemplified by the human mind's procedure of recognizing the truth of the Gödelian sentence, of identifying uncomputable numbers through Turing's diagonal procedure, etc. Since such procedures are strictly defined and are as reliable as any calculations, they are worth to be called computation as well. From the computation in the strict sense, that defined as purely algorithmic (mechanical) process, one distinguishes them with the term "hipercomputation". Now the following questions arise. - Are there undecidable problems (ie. not decidable with appropriate algorithms) in social research as are (according to what is reported esp. By S. Wolfram) in natural sciences? The answer in the negative would impose limitations on computer simulations (as entirely relying on algorithms). - If there are, then we have the next question: can such problems be addressed with hipercomputational procedures? - How such hipercomputational procedures would be related to analog computation (coextensive, everlappiing, etc.)? Another set of issues is stated in terms of tractability of decidable problems, that is, the efficiency of algorithms needed for solutions. As inefficient are regarded those which require more resources (time, memory, etc.) than is available in a foreseeable future. In this context, one discusses methods of such an efficient organizing computational processes to overcome the scarcity of resources; thus parallel, distributive, interactive, etc. computing are used as remedies. The paper claims, hinting at F.Hayek's ideas, that in some social systems (e.g., stock exchange, and free market in general) such an efficient organization of their computational activities spontaneously evolves. And this is the main source of its advantages over the central economic planning (as defended by O. Lange). This noticing (in terms of complexity theory) of analogy between Hayek's point and the current discussion of efficiency of algorithms is what may count as an original contribution of the present paper.

• Publisher: University of Warsaw, Institute of Philosophy
• Journal: Filozofia Nauki
• Year: 2004
• Volume: 12
• Issue: 3-4
• Pages: 5-31

Dates

published

2004-09-01

Contributors

author

Witold Marciszewski