Hacker News new | past | comments | ask | show | jobs | submit login

No, I see no evidence whatsoever for a human being able to solve the halting problem.

"recognizing" it is irrelevant and poorly defined.




Could you describe an algorithm that a human would fail to decide wether it will halt or not?


Show that a human can decide if an arbitrary program terminates. You are the one making an extraordinary claim (and make no mistake about it, the suggestion that humans can be used as oracle machines is an extraordinary claim.)

Simply assuming it is the case because you want it to be the case is not science, it is religion.


I'm just a bit skeptical since I have never encountered a program so far which I couldn't decide whether it would halt or not. You would completely convince me if you could describe such a program. Also, this is not an extraordinary claim. According to Wikipedia, it is an open question:

> It is an open question whether there can be actual deterministic physical processes that, in the long run, elude simulation by a Turing machine, and in particular whether any such hypothetical process could usefully be harnessed in the form of a calculating machine (a hypercomputer) that could solve the halting problem for a Turing machine amongst other things. It is also an open question whether any such unknown physical processes are involved in the working of the human brain, and whether humans can solve the halting problem.

http://en.wikipedia.org/wiki/Halting_problem


When you do that you are doing nothing more than applying heuristics, preforming limited simulation, looking for repeated states. All of these things are things that may be preformed by algorithmic computation. That we don't have IDEs already doing all of this for us is a reflection of nothing more than the current state of machine learning and the relative computational densities of today's electronic computers and the human brain.

Being able to solve the halting problem for programs generally seen in real life programming does not imply in the slightest that you can solve the halting problem for arbitrary programs. Can you look at arbitrary Turing machine tapes (large enough to eliminate the possibility that you are simulating it without realizing it of course) and non-algorithmically decide if they will terminate? Can you in fact do anything non-algorithmically? That is in essence what you are suggesting, the non-algorithmic nature of the human mind.

You are of course not the first to suggest a non-algorithmic mind. The likes of Roger Penrose have also suggested similar things (see his The Emperor's New Mind and later Shadows of the Mind). His reputation is enough to give me serious pause, and the fact that he does not seem to be a dualist further inclines me to listen to what he has to say.

If you want to delve further into this subject I suggest you check out Penrose's work, then read the criticism of it from his peers. Penrose has mounted the most qualified defence of the non-algorithmic mind of which I am aware, but even so acceptance of his thesis is rather rare in academia. It is not light subject matter but the general consensus among experts in the fields which he touches is that in order to support his thesis he made numerous errors. In absence of their expertise, I must defer to their assessment of Penrose's work.


I have never encountered a program so far which I couldn't decide whether it would halt or not. You would completely convince me if you could describe such a program

Does this halt? Assume all variables are arbitrary precision integers.

/* http://en.wikipedia.org/wiki/Perfect_number#Odd_perfect_numb... */

  void searchForOddPerfectNumber() {
    int n = 1, sumOfFactors, factor;

    while (1) {
      sumOfFactors = 0;
      for (factor = 1; factor < n; factor++)
        if (n % factor == 0)
          sumOfFactors += factor;
      if (sumOfFactors == n) break;
      n += 2;
      sumOfFactors = 0;
    }
  }




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: