Even programs have free will

Tarskian

Imagine that you install an app on your phone that can tell you minute by minute what you will be doing at any point in the future along with all possible details?

The existence of this app would prove that you are just an automaton, i.e. a robot. In that case, it would be ridiculous to claim that you have free will. Conversely, you can prove the existence of free will by proving that it is impossible to construct such app.

In fact, there is no app that can tell minute by minute what even any other app will be doing.

Say that you try to construct such oracle app. It inspects the source code of any other app, looks at what inputs the other app will be getting from its environment, and then predicts what the other app will be doing.

Now we construct a pathological app, the thwarter.

The thwarter first asks the oracle what it predicts that it will be doing. The oracle then looks at the source code of the thwarter and at the inputs that it would be getting from the environment, and then predicts what the thwarter will be doing. Upon receiving the answer from the oracle, the thwarter does something else instead, because that is exactly how it was programmed.

The narrative above is pretty much the gist of Alan Turing's proof for the halting problem.

The environment of the oracle and the thwarter is perfectly deterministic. There is nothing random going on. Still, the oracle cannot ever predict correctly what is going to happen next. The oracle is therefore forced to conclude that the thwarter has free will.

noAxioms

Conversely, you can prove the existence of free will by proving that it is impossible to construct such app. — Tarskian

So by your argument, you've used Turing's argument to prove free will. Somehow that doesn't follow from the impossibility of such an app since the app is impossible even in a pure deterministic universe.

Tarskian

Somehow that doesn't follow from the impossibility of such an app since the app is impossible even in a pure deterministic universe. — noAxioms

The natural numbers are also a pure deterministic universe. Most of its truth, however, cannot be predicted by arithmetic theory. A pure deterministic universe can still have free will as long as its theory is incomplete.

The real requirement here, is incompleteness of the theory.

fishfry

The narrative above is pretty much the gist of Alan Turing's proof for the halting problem. — Tarskian

Tarskian, You may be interested in a recent paper by Joel David Hamkins. Turing never proved the impossibility of the Halting problem! He actually proved something stronger than the Halting problem; and something else equivalent to it. But he never actually gave this commonly known proof that everyone thinks he did. Terrific, readable paper. Hamkins rocks.

https://arxiv.org/pdf/2407.00680

In fact, there is no app that can tell minute by minute what even any other app will be doing. — Tarskian

That's too strong a statement. If an app is halted, I can write a program that, given any time t, says, "The program is halted at time t."

Likewise if I'm dead, a program can exactly predict what I'm doing. But of course in that case I wouldn't have much in the way of free will.

The real requirement here, is incompleteness of the theory. — Tarskian

Penrose thinks free will might be a quantum effect in the microtubules of the brain.

https://philosophy.stackexchange.com/questions/3322/the-emperors-new-mind-and-free-will

By the way, humans may or may not have free will.

Programs, by their very nature, do not have free will.

RussellA

In fact, there is no app that can tell minute by minute what even any other app will be doing. — Tarskian

Time is of the essence.

The Thwarter app is not aware (figuratively speaking) of the existence of the Oracle app. All the Thwarter app is aware of is input.

Therefore, we only need to consider the Thwarter app.

Feedback occurs when the output of the Thwarter app then becomes new input. This is a temporal process, in that its output happens at a later time than its input.

The source code of the Thwarter app determines the output from the input using the function F, where output = F (input).

For example, if the input is a set of numbers, such as 3, 5 and 7, the output could be the addition of this set of numbers, such as 15.

At time zero, let there be an input I (1). This input cannot include any subsequent output, as any output happens at a later time.

At time t + 1, the output O (1) can be predicted from the function F operating on input I (1).

At time t + 1, the new input I (2) includes output O (1).

At time t + 2, the new output O (2) can be predicted from the function F operating on input I (2).

At time t + 2, the new input I (3) includes output O (2).

Etc.

At each subsequent time, the output can be predicted from the input. The output is pre-determined by the input.

At any time t + x, the output has been pre-determined by the situation at time zero.

Tarskian

Terrific, readable paper. Hamkins rocks. https://arxiv.org/pdf/2407.00680 — fishfry

Just finished reading it. It is very informative. I must say, though, that it is heavily vested in logic connected to the arithmetical hierarchy. It is still doable but admittedly an obstacle of sorts if you do not use that framework particularly often.

Hamkins acknowledges that the contemporary version of the proof is arguably preferable to Turing's original "detour":

Turing thus showed that the symbol-printing problem is undecidable by mounting a reduction to and through the undecidability of the circle-free problem. But let us illustrate how one may improve upon Turing with a simpler self-referential proof of the undecidability of the symbol-printing problem in the style of the standard contemporary proof of the undecidability of the halting problem. There was actually no need for Turing’s detour through the circle-free problem.

I have tried to turn Hamkins' phrasing of the standard contemporary proof into a narrative:

= Original ==

Namely, assume toward contradiction that the symbol-printing problem were computably decidable, and fix a method of solving this problem. Using this as a subroutine, consider the algorithm q which on input p, a program, asks whether p on input p would ever print 0 as output. If so, then q will halt immediately without printing 0; but if not, then q prints 0 immediately as output. So q has the opposite behavior on input p with respect to printing 0 as output than p has on input p. Running q on input q will therefore print 0 as output if and only if it will not, a contradiction.

== Narrative ==

Namely, assume toward contradiction that the symbol-printing problem were computably decidable, and fix a method of solving this problem. Using the oracle as a subroutine, consider the thwarter program which asks to the oracle whether any program p on input p would ever print 0 as output. If the oracle answers that it will print 0, then thwarter itself will not print 0; but if the oracle says that thwarter doesn't print 0, then thwarter does print 0. Running thwarter on itself as input will therefore print 0 as output if and only if the oracle says that thwarter will not, a contradiction.

For the original circle-free problem, the proof is actually trivially easy.

Say that we call programs with infinite output "infinitist" ("circle-free") and programs with finite output "finitist" ("circular"). Can we list all possible infinitist programs? No, because if we list their infinite output in a table, then we can create a brand new infinite output by flipping the bit on the diagonal, i.e. by diagonalization.

The real difficulty is related to how Turing uses the circle-free problem to prove that the symbol-printing problem is undecidable:

He mounts an unusual kind of reduction, showing that if symbol-printing were decidable, then also the circle-free problem would be decidable, which he had already proved is not the case.

This is not a straightforward reduction of one problem to another, but rather an argument that if one problem were actually computably decidable, then so would be the other.

I agree with Hamkins' take on the matter. I also find the contemporary standard version of the proof much simpler than Turing's original approach. Turing's "unusual kind of reduction" feels like an exercise in painful shoehorning.

By the way, humans may or may not have free will.
Programs, by their very nature, do not have free will. — fishfry

I think that humans have a soul while programs do not. However, since programs also make choices, they can just as humans appear to be "free" in making them or not. That is why I think that it is perfectly possible to analyze free will as a computability problem.

Tarskian

At each subsequent time, the output can be predicted from the input. The output is pre-determined by the input. At any time t + x, the output has been pre-determined by the situation at time zero. — RussellA

Yes, the oracle may perfectly well know that thwarter will do the opposite of what he predicts, but he has committed to his prediction already. It will be too late already.

Benj96

This mirrors the liar paradox:
"The following sentence is true" (the oracle predicting the impending outcome). "The previous sentence is false" (the thwarter doing the opposite to what was predicted to thwart the oracle's veracity/render it false.

It is a dichotomy/pair of mutually cancelling phenomena. The result: lack of utility of either. They're entangled and self defeating.

RussellA

Yes, the oracle may perfectly well know that thwarter will do the opposite of what he predicts, but he has committed to his prediction already. It will be too late already. — Tarskian

The Thwarter app has a source code which specifies how the Thwarter app performs a calculation when input information

The Thwarter app is given an input and performs a calculation to arrive at an answer.

It may be that the Oracle app knows that the answer is contained within the input information.

However, the Thwarter app would only know that the answer was contained in the input information after it had completed its calculation, and then it would be too late to change what type of calculation it had used.

IE, the calculation that the Thwarter app uses cannot be determined by an answer that is only known by the Thwarter app after it has completed its calculation.

fishfry

Just finished reading it. It is very informative. I must say, though, that it is heavily vested in logic connected to the arithmetical hierarchy. It is still doable but admittedly an obstacle of sorts if you do not use that framework particularly often. — Tarskian

I enjoyed it.

Hamkins acknowledges that the contemporary version of the proof is arguably preferable to Turing's original "detour":

Turing thus showed that the symbol-printing problem is undecidable by mounting a reduction to and through the undecidability of the circle-free problem. But let us illustrate how one may improve upon Turing with a simpler self-referential proof of the undecidability of the symbol-printing problem in the style of the standard contemporary proof of the undecidability of the halting problem. There was actually no need for Turing’s detour through the circle-free problem.

I have tried to turn Hamkins' phrasing of the standard contemporary proof into a narrative:

[... details omitted]
— Tarskian

You have made an impressively detailed reading of the article, way more than I did.

I think that humans have a soul while programs do not. — Tarskian

I am in complete agreement. But just try to explain that to the simulation theorists, the mind-uploading freaks, the singularitarians, the AGI proponents, etc. They have the mindshare these days.

However, since programs also make choices, they can just as humans appear to be "free" in making them or not. That is why I think that it is perfectly possible to analyze free will as a computability problem. — Tarskian

Hmmm. Let me mull that over. I don't agree. Computability, by its nature, is deterministic. Whatever free will is, it is not computable.

Tarskian

Hmmm. Let me mull that over. I don't agree. Computability, by its nature, is deterministic. Whatever free will is, it is not computable. — fishfry

Computability may be deterministic but is fundamentally still unpredictable too. It is generally not possible to predict what a program will be doing at runtime:

https://en.wikipedia.org/wiki/Rice%27s_theorem

In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable.

A semantic property is one about the program's behavior (for instance, "does the program terminate for all inputs?"), unlike a syntactic property (for instance, "does the program contain an if-then-else statement?"). A non-trivial property is one which is neither true for every program, nor false for every program.

The theorem generalizes the undecidability of the halting problem. It has far-reaching implications on the feasibility of static analysis of programs. It implies that it is impossible, for example, to implement a tool that checks whether a given program is correct, or even executes without error.

The theorem is named after Henry Gordon Rice, who proved it in his doctoral dissertation of 1951 at Syracuse University.

A deterministic system is unpredictable when its theory is incomplete. There is no need for randomness for a system to be unpredictable. Free will is essentially the same as unpredictability.

fishfry

Computability may be deterministic but is fundamentally still unpredictable too. It is generally not possible to predict what a program will be doing at runtime: — Tarskian

I am not sure if Rice's theorem means what you say it does.

If you give me a program, say its listing printed out on paper; and you give me its inputs; and you give me a lot of pencils, paper, and time; I can deterministically and with no ambiguity determine exactly what it's going to do. I can not imagine this being false, and therefore Rice must be full of beans! :-)

A deterministic system is unpredictable when its theory is incomplete. There is no need for randomness for a system to be unpredictable. Free will is essentially the same as unpredictability. — Tarskian

Not how I understand this. A chaotic system is deterministic yet unpredictable. Nothing to do with incompleteness. There's no free will, none whatsoever, in a chaotic system.

Tarskian

If you give me a program, say its listing printed out on paper; and you give me its inputs; and you give me a lot of pencils, paper, and time; I can deterministically and with no ambiguity determine exactly what it's going to do. I can not imagine this being false, and therefore Rice must be full of beans! — fishfry

You will never predict correctly what thwarter is going to do.

A chaotic system is deterministic yet unpredictable. Nothing to do with incompleteness. There's no free will, none whatsoever, in a chaotic system. — fishfry

When you put thwarter in that chaotic system, you suddenly have something freely making decisions while you can impossibly predict what decisions it will make.

Free will is a property of a process making choices. If it impossible to predict what choices this process will make, then it has free will.

flannel jesus

You will never predict correctly what thwarter is going to do. — Tarskian

What makes you convinced thwarter is a genuinely possible program? Has anyone programmed one?

flannel jesus

↪fishfry

you kind of contradict the first half of your post here with the second half. In the first half, you speak as if something being deterministic is basically synonyms with it being predictable, but in the second half you acknowledge that a chaotic system could be deterministic but unpredictable.

If a chaotic system can be deterministic but unpredictable, then you should be able to imagine software that is chaotic, and thus deterministic and unpredictable, no?

I think there's a subtly shifting meaning for the word "unpredictable" that's at play there.

Tarskian

What makes you convinced thwarter is a genuinely possible program? Has anyone programmed one? — flannel jesus

Thwarter is trivially easy to implement. On input of string "halt" it prints "loop forever" and on input "loop forever" it prints "halt".

So, if the prediction (which is the input string) is that Thwarter will print "halt" or "loop forever", it won't.

The problem is rather to implement oracle. Example:

https://github.com/Solidsoft-Reply/Halting-Problem

flannel jesus

ah my bad, didn't read the op carefully enough.

I really don't see that as free will in any meaningful sense.

Tarskian

I really don't see that as free will in any meaningful sense. — flannel jesus

It is a contorted example.

It is accepted as proof, however, that no oracle can exist that can predict what choices programs will make.

Even in a perfectly deterministic environment, free will can still exist, as long as its theory is incomplete.

Therefore, we don't even need the physical universe to be nondeterministic for free will to be possible. It just needs to be incomplete.

flannel jesus

↪Tarskian

I don't agree that free will has anything to do with oracle-like programs at all

Tarskian

↪flannel jesus

incompatibilism implies that if the oracle exists, free will doesn't.

flannel jesus

↪Tarskian

no, incompatibilism implies that if determinism is true, free will doesn't exist - but you explained yourself that this oracle can be impossible even if determinism is true, no?

So one can imagine a world where determinism is true, this oracle is impossible, and free will doesn't exist because determinism is true, regardless of this oracle.

Tarskian

no, incompatibilism implies that if determinism is true, free will doesn't exist — flannel jesus

incompatibilism implies that if predeterminism is true, free will doesn't exist

There is a massive difference between predeterminism and deterministic systems. If a deterministic system is incomplete, its future is not predetermined.

So one can imagine a world where determinism is true, this oracle is impossible. — flannel jesus

It is exactly in a predetermined world, that the oracle can make flawless predictions.

The universe consisting of just the oracle app and the thwarter app, however, is not predetermined because of its incompleteness. The construction theory of this world is capable of arithmetic. That is enough to make it incomplete and therefore not possibly predetermined.

It is perfectly possible to deterministically build machines that are not predetermined.

flannel jesus

↪Tarskian

what is this incomplete determinism? I googled it but none of the results seemed like what you're talking about.

Tarskian

what is this incomplete determinism? — flannel jesus

Predeterminism implies that the system's theory is complete. In that case, every true fact about the system can be derived from its theory. If this is not possible, then the system's theory is incomplete.

For example, the arithmetic theory about the natural numbers is incomplete.

https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems

The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an effective procedure (i.e. an algorithm) is capable of proving all truths about the arithmetic of natural numbers.

The arithmetic of the natural numbers is obviously a deterministic system. There is nothing random about it. Still, its truth is mostly unpredictable.

flannel jesus

↪Tarskian

I think you've invented your own special kind of incompatibilism here. If you ask an incompatibilist if they think free will is possible in a universe that is deterministic, but in which an oracle is impossible, I guarantee you 99%+ of incompatibilists will say "screw oracles, free will is incompatible with determinism period".

I don't think anything about the oracle or the thwarter says anything interesting about free will at all, personally, i think it's a red herring.

Tarskian

I guarantee you 95%+ of incompatibilists will say "screw oracles, free will is incompatible with determinism period". — flannel jesus

I use the term "predeterminism" instead of "determinism" because of the possible confusion with the term "deterministic system".

https://en.wikipedia.org/wiki/Predeterminism

Predeterminism is the philosophy that all events of history, past, present and future, have been already decided or are already known (by God, fate, or some other force), including human actions. Predeterminism is closely related to determinism.

https://en.wikipedia.org/wiki/Deterministic_system

In mathematics, computer science and physics, a deterministic system is a system in which no randomness is involved in the development of future states of the system.

A deterministic system that is incomplete is not predetermined. Further confusion is also caused by tying the term "determinism" to "causality":

https://en.wikipedia.org/wiki/Determinism

Determinism is the philosophical view that all events in the universe, including human decisions and actions, are causally inevitable.

Causality is not a usable notion in mathematics. It is replaced by "provable from its theory". We don't need to know what the individual causes are for a particular fact. We don't care about that. We just need to know that the system can correctly predict the fact. Hence, the idea that all facts are "causally inevitable" translates into all facts being "provable from theory". So, the term "determinism" in mathematical terms means "completeness". It does not mean "deterministic system".

There are two fields involved here: metaphysics and mathematics. The vocabulary is not completely aligned.

flannel jesus

↪Tarskian

I don't think any of that goes any distance towards demonstrating what I said was incorrect. Incompatibilists say free will is incompatible with determinism, not oracles

Tarskian

I don't think any of that goes any distance towards demonstrating what I said was incorrect. Incompatibilists say free will is incompatible with determinism, not oracles — flannel jesus

The existence of a functioning oracle is equivalent to determinism (with the notion of determinism equivalent to the notion of completeness). The oracle fails. It doesn't function. Therefore, there is no determinism.

Asserting incompatibilism, as a notion in metaphysics, translates into proving the impossibility of constructing an oracle, as a notion in computer science. It is effectively equivalent. The difficulty here is that we are mapping concepts from one field to another.

flannel jesus

with the notion of determinism equivalent to the notion of completeness — Tarskian

So then when you were talking about incomplete determinism, you were... what? What is that? An oxymoron? Nonsense? A contradiction? What is that?

Tarskian

So then when you were talking about incomplete determinism — flannel jesus

incomplete deterministic system.

flannel jesus

Asserting incompatibilism, as a notion in metaphysics, translates into proving the impossibility of constructing an oracle, as a notion in computer science. It is effectively equivalent. — Tarskian

This is just factually untrue. You've got chaos theory which makes future-predicting oracles impossible, to start with.

Even programs have free will

Welcome to The Philosophy Forum!

Categories

More Discussions