Halting Problem and Free Will

[kenstauffer 0]

I am a materialist when it comes to the mind and consciousness. Of course, this puts me at odds each time "free will" is mentioned in Objectivism. How can a materialistic viewpoint escape the inherent predeterminism in such a view?

Some objectivists have "resolved" this issue by citing the axiomatic nature of free will, and thus ending all further inquiry into the subject. (but existence is an axiom too, but that doesn't mean chemists and atom smashers are wasting their time). Others have reconciled free will with materialism by proposing a new force of nature that allows consciousness to manipulate matter.

See my previous post to see how I believe free will is consistent with my materialism. For this new topic I just want to explore the halting problem, and how it is solvable for Finite Automata

The Halting Problem:

The halting problem arises in the context of turing machines that have inifinite storage capacity. It has been proved that no general algorithm can be written that will determine if an arbitrary algorithm will halt. (I.e, you cannot predict the algorithm's behavior. Can you smell the parellels with free will?).

The Halting Problem for finite Automata:

If you have a turning machine with a capcity for N states, then I can build a larger turning machine that simulates the smaler one. Whenever I detect a repeated state then I know the algorithm DOESN'T halt. But if the simulated program reaches a HALT state, then I know the algorithm halts (duh!). Futher, (and most important) my larger computer will always terminate and give an answer.

Since the finite nature of consciousness is not a debated fact in Objectivism, then I believe free will need not be incongruent with materialism.

[piz 0]

The Halting Problem:

The halting problem arises in the context of turing machines that have inifinite storage capacity. It has been proved that no general algorithm can be written that will determine if an arbitrary algorithm will halt. (I.e, you cannot predict the algorithm's behavior. Can you smell the parellels with free will?).

The Halting Problem for finite Automata:

If you have a turning machine with a capcity for N states, then I can build a larger turning machine that simulates the smaler one. Whenever I detect a repeated state then I know the algorithm DOESN'T halt. But if the simulated program reaches a HALT state, then I know the algorithm halts (duh!). Futher, (and most important) my larger computer will always terminate and give an answer.

Since the finite nature of consciousness is not a debated fact in Objectivism, then I believe free will need not be incongruent with materialism.

←

Two points here:

1. Seems to me that your example is a foregone conclusion: if the machine has only N states, then it must repeat or terminate. The problem comes when the larger Turing machine is used to attempt to determine whether or not it will itself ever terminate. If I recall correctly, that's the basis of the proof you mention.

2. Given the aroma of parallels , you might be interested in a book, A New Kind of Science, by Stephen Wolfram. Fascinating treatment of automata, complexity arising from simplicity, and the usefulness of computer models in understanding natural phenomena. Ultimately he comes to an erroneous conclusion about free will (I won't "spoil the ending" by getting into it here, unless someone asks me to), but everything up to that point is quite good. Also, the book was published about ten years too late - much of what Wolfram apparently originated had already seeped into more general knowledge by the time he got around to getting the book out, so it doesn't seem as revolutionary as he claims it to be. Given when he did the original work, it was revolutionary, but from today's perspective, not so much.

[Free Capitalist 0]

Ken, you make one big assumption in your post - that the human brain is a turing machine, an assumption which you cannot make. Plus, among other things, human beings can solve the Halting Problem; in fact programmers do it every day, or how else do you think they are creating and debugging all those complicated computer programs? Clearly they can determine when a loop will or will not terminate.

[Stephen Speicher 0]

Since the finite nature of consciousness is not a debated fact in Objectivism, then I believe free will need not be incongruent with materialism.

←

What exactly do you mean by "materialism?" And while we are at it, in what particular sense do you refer to the "finite nature of consciousness?"

[Stephen Speicher 0]

...Given the aroma of parallels , you might be interested in a book, A New Kind of Science, by Stephen Wolfram. Fascinating treatment of automata, complexity arising from simplicity, and the usefulness of computer models in understanding natural phenomena.

I have the greatest respect towards Wolfram for his development of Mathematica his very clever mathematics computer system. And Wolfram certainly possesses a respectable intellect -- he was the youngest ever Professor at Caltech, where he worked in particle physics -- but in attempting to become a theorist with his cellular automaton, he completely misses the mark.

The notion of cellular automaton -- geometric arrays of cells which determine their state according to rules -- goes back fifty years to the great mathematician John von Neumann. This notion of the universe as a cellular automaton was originated before Wolfram by a flamboyant character I am acquainted with, Ed Fredkin. I find the notion to be so bizarre -- and the claims made by Wolfram to be so outrageous -- that it is difficult to take the basic premise seriously. The universe is not a series of discrete biological and physical cells, and space and time are not discrete as in a cellular automaton.

The book itself is a wonderment of fascinating computational ideas, with marvelously constructed and beautiful examples, but a "new kind of science" it is not. Contrary to Stephen Wolfram's perspective, ideas and mathematics will remain as the mainstay of science.

[kenstauffer 0]

What exactly do you mean by "materialism?" And while we are at it, in what particular sense do you refer to the "finite nature of consciousness?"

←

My saying "finite nature of consciousness" was nothing more than saying "finite nature of beach balls". It sounds deep and profound, but is really just an application of the law of identity to consciousness. I mentioned it because my view that the mind is a large turning machine with a finite number of states.

And this addresses your first question, what do I mean by materialism? I view consciousness as an emergent phenomenon from matter, where matter has strict cause/effect billard-ball like properties. But this view is not Objectivism, because you cannot derive consciousness from non-consciousness.

It was my hope that I could keep my materialistic tendencies and the axiomatic nature of consciousness, and while we are at it, explain free will. (and all in a short 100 word post on an internet forum!)

By the way, this points out two of my errors (mentioned by Dr. Binswanger in his lecture 'The Metaphysics of Consciousness':

1. equating volition with consciousness.

2. trying to derive consciousness from non-consciousness.

[kenstauffer 0]

Ken, you make one big assumption in your post - that the human brain is a turing machine, an assumption which you cannot make.

←

Yes, that is one of the biggies of the AI community. Is the mind just a complicated computer with more states? It is also the assumption of the church-turning thesis that any computable function must also be computable by a turning machine (no exceptions). That's a huge assumption, and no counter example has so far been found to contradict it. I am not claiming this gives me a right to my "brain equals turning machine" viewpoint, but that's where I get it from.

... human beings can solve the Halting Problem; in fact programmers do it every day, or how else do you think they are creating and debugging all those complicated computer programs? Clearly they can determine when a loop will or will not terminate.

←

Human beings cannot solve the halting problem. Remember that the halting problem applies to all algorithms. This would mean that I could give a human any algorithm, and if they can solve the halting problem, then they can always report: "YES" the loop terminates, or "NO" the loop goes on forever.

If this were true, I could give a human a simple loop that iterates over all the integers (starting at 0) and terminates only when fermat's last theorem is FALSE. If a human told me that this loop terminates, then I have a refutation of Fermat's, if the human told me the loop goes on forever they have established the truth of Fermat's last theorem.

In otherwords, being able to solve the halting problem, implies humans could trivially solve all currently unsolved problems in number theory.

(Fermat's was a bad example as it HAS been solved in this specific case, but subsitute any currently unsolved problem in number theory to make my example compelling again)

[dougclayton 0]

Ken, you make one big assumption in your post - that the human brain is a turing machine, an assumption which you cannot make. Plus, among other things, human beings can solve the Halting Problem; in fact programmers do it every day, or how else do you think they are creating and debugging all those complicated computer programs? Clearly they can determine when a loop will or will not terminate.

←

Although the brain is not reducible to a Turing machine, it can be considered as containing a bounded Turing machine (or simulating one, if you prefer), in that you can step through an algorithm in your head. (Of course, it goes without saying that you can do other things that are not algorithmic.)

Furthermore, humans cannot solve the Halting Problem, because there are some programs whose termination is unknown. Programmers determine if particular programs terminate, but cannot determine if any arbitrary program will.

[Stephen Speicher 0]

My saying "finite nature of consciousness" was nothing more than saying "finite nature of beach balls". It sounds deep and profound, but is really just an application of the law of identity to consciousness. I mentioned it because my view that the mind is a large turning machine with a finite number of states.

This answer illustrates why I asked "in what particular sense." You were smuggling in your Turing machine notion when you said:

Since the finite nature of consciousness is not a debated fact in Objectivism, then I believe free will need not be incongruent with materialism.

This latter conclusion is unconnected to the former statement about consciousness, except via the magic of your Turing machine. (Incidentally, as an aside, what is this fascination with Turing machines? What do they have to do with reality?)

And this addresses your first question, what do I mean by materialism? I view consciousness as an emergent phenomenon from matter, where matter has strict cause/effect billard-ball like properties. But this view is not Objectivism, because you cannot derive consciousness from non-consciousness.

I think you are confused about this. Materialism is a denial of consciousness, in that it equates conscious processes identically with physical states of the brain. They are one and the same. Your reference to "emergent phenomenon" does not fit with this. And, as I understand the Objectivist view, consciousness is a sort of "emergent phenomenon from matter" in that the brain gives rise to consciousness.

It was my hope that I could keep my materialistic tendencies and the axiomatic nature of consciousness, and while we are at it, explain free will. (and all in a short 100 word post on an internet forum!)

What's wrong with the view I have stated here many times?

[kenstauffer 0]

Stephen your reply is much appreciated. In particular,

What's wrong with the view I have stated here many times?

←

That's a great question. One I haven't asked myself (but should have) for ages.

Somewhere, long ago, I got stuck on this turing/godel/computer analogy and have not been willing to let it go. Part of the reason is that I only half heartily accepted the Objectivist position on volition. "volition" never jived with my scientific billard-ball view of the universe.

Also, when I was exposed to the ideas of Godel/Turning/Halting problem in college, I was blown away by the results. Again, my billard-ball view of the world made it hard for me to accept the fact that a formal notation powerful enough to express arithemetic is insufficient to prove ALL true statements of that notation. (Godel's incompletness)

[kenstauffer 0]

Stephen your reply is much appreciated. In particular,

That's a great question. One I haven't asked myself (but should have) for ages.

Somewhere, long ago, I got stuck on this turing/godel/computer analogy and have not been willing to let it go. Part of the reason is that I only half heartily accepted the Objectivist position on volition. "volition" never jived with my scientific billard-ball view of the universe.

Also, when I was exposed to the ideas of Godel/Turning/Halting problem in college, I was blown away by the results. Again, my billard-ball view of the world made it hard for me to accept the fact that a formal notation powerful enough to express arithemetic is insufficient to prove ALL true statements of that notation. (Godel's incompletness)

←

This just occured to me,

My argument is very similar to Penrose's (The Emperor's New Brain) on the subject of consciousness.

1. QM is wierd

2. Consciousness is wierd

3. Therefore consciousness is based on QM

My argument is:

1. Turing/Godel/Halting Problem is wierd

2. Consciousness is wierd

3. Therefore consciousness is based on Turing/Godel.

[piz 0]

I have the greatest respect towards Wolfram for his development of Mathematica his very clever mathematics  computer system. And Wolfram certainly possesses a respectable intellect -- he was the youngest ever Professor at Caltech, where he worked in particle physics -- but in attempting to become a theorist with his cellular automaton, he completely misses the mark.

←

I agree, though that might not have been obvious in my post.

The notion of cellular automaton -- geometric arrays of cells which determine their state according to rules -- goes back fifty years to the great mathematician John von Neumann. This notion of the universe as a cellular automaton was originated before Wolfram by a flamboyant character I am acquainted with, Ed Fredkin. I find the notion to be so bizarre -- and the claims made by Wolfram to be so outrageous -- that it is difficult to take the basic premise seriously. The universe is not a series of discrete biological and physical cells, and space and time are not discrete as in a cellular automaton.

←

I think there are certain phenomena that exhibit behavior similar to cellular automata (Wolfram's biological examples, such as patterns in seashell formation, are very interesting). But that doesn't prove that the natural mechanisms themselves are cellular automata, just that it's possible to manufacture algorithms that behave to some extent like nature, which is far from a new idea. And you're right - the universe is not a cellular automaton. By theorizing that it is, Wolfram makes the mistake of reifying the description, like someone who might claim that E=mc^2 somehow exists and drives the universe rather than merely describing what reality does on its own. It's no wonder, then, that bizarre things follow.

The book itself is a wonderment of fascinating computational ideas, with marvelously constructed and beautiful examples, but a "new kind of science" it is not. Contrary to Stephen Wolfram's perspective, ideas and mathematics will remain as the mainstay of science.

←

I'm not convinced that algorithms should be excluded, a priori, as alternatives to equations for describing natural phenomena. But Wolfram's posits that we can "experiment," with computer systems taking the place of reality, and draw valid conclusions about the real world. Well, environmentalist "science" makes the same claim, and we know the results of that. Wolfram's erroneous conclusions about volition are his own most glaring example of his mistake.

[Stephen Speicher 0]

This just occured to me,

My argument is very similar to Penrose's (The Emperor's New Brain) on the subject of consciousness.

←

In that case, you are really in trouble.

Penrose is a brilliant mathematician, but a horrible theoretician.

[Stephen Speicher 0]

I'm not convinced that algorithms should be excluded, a priori, as alternatives to equations for describing natural phenomena.

I doubt that anyone would want to exclude such algorithms out of hand. But, in essence, the algorithms are, at best, evolutionary, not descriptive. Physics is concerned with causal mechanisms, and an evolutionary prescription offers little to nothing in the way of physical insight. Proper equations can be directly tied to physical reality, with elements of the equation describing, characterizing, and otherwise connecting abstractions to the concrete world.

[Bryan 0]

Human beings cannot solve the halting problem. Remember that the halting problem applies to all algorithms. This would mean that I could give a human any algorithm, and if they can solve the halting problem, then they can always report: "YES" the loop terminates, or "NO" the loop goes on forever.

In the context of programming, when coding a loop, you give it a limit on which if it reaches that limit it will terminate. By looking at a loop, I could tell you the maximum value that the loop will reach. If it were an infinite loop, I could execute it and tell you exactly when it terminates, which would be when I hit ctrl-c to kill the process .

If this were true, I could give a human a simple loop that iterates over all the integers (starting at 0) and terminates only when fermat's last theorem is FALSE. If a human told me that this loop terminates, then I have a refutation of Fermat's, if the human told me the loop goes on forever they have established the truth of Fermat's last theorem.

This has more to do with time and resource restrictions than a human being's inability to solve the problem.

[kenstauffer 0]

In the context of programming, when coding a loop, you give it a limit on which if it reaches that limit it will terminate. By looking at a loop, I could tell you the maximum value that the loop will reach.

←

But in this case the human is not doing anything that a machine couldn't programmed to do. In a context in which the algorithm parameters are limited (i.e has finite number of states.), then a machine can solve the halting problem too.

[Free Capitalist 0]

Can you provide one such algorithm where a human cannot figure out if it will terminate or not (assuming we know already have all of the variables beforehand)?

[kenstauffer 0]

Can you provide one such algorithm where a human cannot figure out if it will terminate or not (assuming we know already have all of the variables beforehand)?

←

This is my implementation for the Goldbach conjecture..

   function PRIME(n)
  -- True if n is prime
  -- (This algorithm terminiates for all n)

	function GOLDBACH(n)
  -- True if 'n' is the sum of 2 primes, else False.
  -- (This algorithm terminiates for all n)
	begin
  for x = 1 to n
  	for y = 1 to n
    if PRIME(x) and PRIME(y) and (x + y) = n then
    	return TRUE
  return FALSE;
	end

Does this loop terminate?

	halt := False
	n := 2
	repeat
  if GOLDBACK(n) then
  	halt := True;
  n := n + 2;
	until halt = True

[kenstauffer 0]

I screwed up... Arghhh. I need to change the final loop to be "not GOLDBACH()".

Does this loop terminate?

	
        halt := False
        n := 2
        repeat
             if NOT GOLDBACK(n) then
                      halt := True;
           
              n := n + 2;
        until halt = True

[Bryan 0]

I screwed up... Arghhh. I need to change the final loop to be "not GOLDBACH()".

Does this loop terminate?

←

Out of boredom I coded it in Python:

def prime(y):
    x = y / 2
    while x > 1:
        if y % x == 0:                 # remainder
            return False
            break                      # skip else
        x = x-1
    else:                              # normal exit
        return True


def goldbach(n):
    for x in range(n):
        for y in range(n):
            if prime(x) and prime(y) and (x+y)==n:
                return True
    return False
                
x=0;n=2

while(x==0):
    if goldbach(n)==False:
        print 'True',n
        x=1
    else:
        n+=2
        print n

N got up to about about 1500 then I got tired of looking at it .

You said that GOLDBACH(n) terminates for all n, so that loop wouldn't terminate because it is looking for an 'n' that terminates on NOT GOLDBACH(n).

[kenstauffer 0]

It is unknown if the loop terminates, as the goldbach conjecture is still unsolved.

(My comment for the GOLDBACH said it always terminates, but that doesn't mean it always returns TRUE, if it is found to return FALSE for any 'n' input, then the conjecture is false, so far this function has returned TRUE for values as high as 2 x 10^17)

[Bryan 0]

It is unknown if the loop terminates, as the goldbach conjecture is still unsolved.

(My comment for the GOLDBACH said it always terminates, but that doesn't mean it always returns TRUE, if it is found to return FALSE for any 'n' input, then the conjecture is false, so far this function has returned TRUE for values as high as 2 x 10^17)

←

Doesn't this just have to do with the nature of prime numbers? There is no (known) "maximum prime number". The goldbach returns true if 'n' is the sum two prime numbers. If there is no maximum prime number, then every even number can be expressed as the sum of two prime numbers.

[kenstauffer 0]

Doesn't this just have to do with the nature of prime numbers?

←

Yes. But re-casted in the form of an algorithm. If a human can solve the halting problem then a human should be able to examine this and definitatively report YES it halts or NO it does not.

There is no (known) "maximum prime number".

←

Yep, and this loop explores all even numbers starting with '4' and the loop only halts when it discovers an even number that cannot be expressed as the sum of two prime numbers.

If there is no maximum prime number, then every even number can be expressed as the sum of two prime numbers.

←

If that's true then you are a millionaire.

[Bryan 0]

If there is no maximum prime number, then every even number can be expressed as the sum of two prime numbers.

If that's true then you are a millionaire.

←

Which part isn't true? That there is no maximum prime number, or that every even number can be expressed as a sum of two prime numbers?

[kenstauffer 0]

Primes are proven to go on forever.