1

The Halting problem (I think) is the problem of trying to find a general algorithm for determining if a specific program will halt within a computer system. It's been shown a general procedure for this doesn't exist (I think). Does this apply to the organisational abilities of the mind? Any information management system like the mind/brain has to orchestrate when certain programs are to 'run' or be changed and if it can't always tell when a program is going to halt how can the system organize itself??

  • 2
    The Turing machine is a mathematical model of computing, and also of human computing. To extrapolate that it is a model of human mind is a very very big extrapolation. Current "general purpose computers" are quite effective implementation of the mathematical concept of universal Turing machine (with obvious limitations regarding the tape ...) and they works quite well. – Mauro ALLEGRANZA Apr 26 '14 at 9:21
  • 1
    It's not simply that a general solution isn't known, but that it can't exist; the halting problem is "undecidable" (over TMs) – Joseph Weissman Apr 26 '14 at 13:26
  • You should update this question with a more accurate description of the halting problem. – James Kingsbery Apr 30 '14 at 17:43
3

The halting problem says nothing directly about minds. It says something about recursive sets and recursively enumerable sets. A recursively enumerable set is a set of integers that can be generated (enumerated) by a Turing machine. (We can create a Turing machine that will print each member of the set on its tape.)

Turing's theorem is:

given any encoding of integers into computing machines, the set of integer pairs

K = { < i, j > | program i halts when run on input j }

is recursively enumerable while its complement

not(K) = { < i, j > | program i does not halt when run on input j }

is not.

It should not be surprising that there are many sets of integers (or of integer pairs) that are not recursively enumerable. There are only countably many integers (and only countably many integer pairs), thus only countably many Turing machines encodable by the integers. But the set of all sets of integers (the power set of the integers), is uncountably infinite. So "most" sets of integers are not recursively enumerable.

Turing's proof is by diagonalization, and is similar to the liar's paradox.

Let's look at the set doesntHaltOnItself = { i | program i does not halt when run on input i }

Can we construct a Turing machine, H, that halts and prints "accept" for all i in doesntHaltOnItself, and otherwise (if i halts when run on i) runs forever? Suppose so. Is H in doesntHaltOnItself? Suppose H is in doesntHaltOnItself. Then when H is run on input H it does not halt. But for all i in doesntHaltOnItself H was supposed to halt and print "accept". So H must not be in doesntHaltOnItself. But that means that when H runs on itself it halts. But when H is run on a program that halts on itself it is supposed to run forever. Also a contradiction. So our assumption that we could construct H is incorrect. Note that doesntHaltOnItself is essentially a subset of not(K), so not(K) is not recursively enumerable.

Turing's theorem, like Gödel's theorem (and Cantor's diagonalization procedure), tells us something deep about the limits of logic, set theory and mathematics.

Whether Turing's theorem (or Gödel's theorem (or the cardinality of power sets)) tells us anything interesting about human minds depends on a whole other set of assumptions (like whether or not you believe that consciousness depends on the ability to enumerate sets that are not recursively enumerable.)

Your question was specifically about the connection between Turing's theorem and "self organization". I see no connection between the ability to "self organize" and the ability to enumerate sets that aren't recursively enumerable. It's not even apparent to me that a self organizing system needs to be able to enumerate all the recursively enumerable sets (and certainly not any of the non finite recursively enumerable sets.)

  • 1
    I've never heard that the proof shows that the set of programs that don't halt is uncountably infinite. Where are you getting that from? – senderle Apr 26 '14 at 18:41
  • @senderle: :$ I was getting that from being wrong. I've corrected my answer. Thanks for pointing out my error! – Wandering Logic Apr 26 '14 at 22:39
  • 1
    I suppose so. It sounds like you are describing a computer operating system, like Linux. The "halting problem" doesn't prohibit you from observing that a process has halted. Nor does it prohibit you from terminating a process that is currently running (hasn't halted on its own.) Nor, for that matter, does it prohibit you determining whether some programs don't terminate. Nor does it say that the programs that you can't determine whether or not they halt are required for any cognitive process. – Wandering Logic Apr 28 '14 at 11:04
  • 1
    Actually, assuming you believe that everyone (including yourself) will eventually die, then you do know that every physical process involved in the human mind eventually halts. So the halting problem is (as far as I can determine) irrelevant to the question of human cognition. – Wandering Logic Apr 28 '14 at 11:08
  • 2
    @user128932, Wandering Logic's comment above gives an excellent list of things that Turing's proof does not prohibit. I'll add one more: it doesn't apply to an inconsistent formal system. And the mind seems to operate in ways that are less rigorous than the kinds of formal systems that Turing was analyzing. Therefore the human mind may not be subject to the same restrictions -- not because it somehow "transcends" them, but because it doesn't necessarily give consistent results. (As we can see by the fact that people accept invalid "proofs" all the time!) – senderle Apr 28 '14 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.