6533b858fe1ef96bd12b56b3

RESEARCH PRODUCT

How to simulate free will in a computational device

subject

description

Since we believe that human brain is not a purely deterministic device merely reacting to the environment but rather it is capable to a free will, Theoretical Computer Science has also tried to develop a system of notions generalizing determinism. Nondeterministic and probabilistic algorithms were the first generalizations. Nondeterministic machines constitute an important part of the Theory of Computation. Nondeterminism is a useful way to describe possible choices. In real life there are many regulations restricting our behavior. These regulations nearly always leave some freedom for us how to react. Such regulations are best described in terms of nondeterministic algorithms. Nondeterministic algorithms prescribe at every specific moment what actions are allowed. A good example might be the instructions what the emergency health service is supposed to do and what they are not supposed to do. If the doctor takes too much liberty, he or she may save the patient but in such a case the doctor is under the threat of legal prosecution. However nobody has tried to build a nondeterministic electronic computer because a real-life computer has to make exactly one choice in every situation but nondeterminism does not give and it is not able to give any mechanism of how to perform choices. On the other hand, comparison of time and space complexity of deterministic and nondeterministic algorithms is one of the central topics in Theoretical Computer Science nowadays. Probabilistic algorithms were first used during WW2 for simulation and numerical analysis. Probabilistic Turing machines were introduced by de Leeuw et al. in [28]. Informally, probabilistic Turing machines differ from their deterministic counterparts only in one way. The probabilistic machines can at any moment make statistically independent random equiprobable choices, i.e. they can at any moment ”to toss a coin”. An arbitrary probabilistic machine can have an undesirable property to produce various results with rather close probabilities. Hence it is usually additionally demanded that the machine is to be programmed in such a way that for every input there is only one output value the probability of which exceeds so-called cut-point,usually the value 12 . For practical applicability of a probabilistic