-4
$\begingroup$

I think that Alan Turing's solution for the "halting" problem might be wrong.

Turing's main premise is wrong, he assumed the only way to check whether a program halts is to run it. He didn't consider that it's possible to determine whether any given program will ever halt by parsing and analyzing its code without running it.

I wrote a simple program in Javascript to demonstrate that:

You can run it in the browser's console

/** 
* @param {any} program // either a parsed evaluated tree or a simple statement
* @returns {boolean}
*/
function checkProgramHalts (program) {
  // If the input is a simple statement (e.g. number 5, string '5', boolean true), 
  // rather than a parsed evaluated program tree, return true, since 
  // simple statements always halt
  if (['number', 'string', 'boolean'].includes(typeof program)) {
    return true
  }

  // For simplicity, using a simple code analyzer,
  // that can only check simple single type programs:
  // - declare var condition in line 1
  // - run while loop in line 2
  // - change condition var value in line 3
  var programEnteredInfiniteLoop = false
  program.statements.forEach(statement => {
    if (statement.operator === 'while') {
      if (eval(statement.nestedCode.varChange.varValue) === true) {
        programEnteredInfiniteLoop = true
      }
    }
  })
  return programEnteredInfiniteLoop ? false : true
}

// Program with an infinite loop
var parsedEvaluatedProgramTree1 = {
  statements: [
    {
      operator: 'var',
      varName: 'condition',
      varValue: 'true'
    },
    {
      operator: 'while',
      condition: '(condition)',
      nestedCode: {
        varChange: {
          varName: 'condition',
          varValue: 'true'
        }
      }
    }
  ]
}


// Program without infinite loops
var parsedEvaluatedProgramTree2 = {
  statements: [
    {
      operator: 'var',
      varName: 'condition',
      varValue: 'true'
    },
    {
      operator: 'while',
      condition: '(condition)',
      nestedCode: {
        varChange: {
          varName: 'condition',
          varValue: 'false'
        }
      }
    }
  ]
}

// - test1: true: simple statement 'string' will halt
// - test2: false: program with infinite loop will never halt
// - test3: true: program without infinite loops will halt
// - test4: true: simple statement 'boolean' will halt
var test1 = checkProgramHalts('5') 
var test2 = checkProgramHalts(parsedEvaluatedProgramTree1)
var test3 = checkProgramHalts(parsedEvaluatedProgramTree2)
var test4 = checkProgramHalts(checkProgramHalts(parsedEvaluatedProgramTree1)) 
console.log(test1)
console.log(test2)
console.log(test3)
console.log(test4)

In a real world program, we would use an advanced compiler that evaluates all used expressions and tracks all variable changes to guarantee that the state of all statements is known and all runtime errors are considered.

$\endgroup$
7
  • 1
    $\begingroup$ The Halting problem is not about deciding whether program halts by simulating it. The proof of undecidability of the halting problem shows that there is no Turing machine that can decide whether a given input program halts. This applies regardless of the inner workings of the Turing machine, which might or might not simulate the input program. $\endgroup$
    – Steven
    Commented Jul 4, 2021 at 21:59
  • $\begingroup$ @Steven what do you mean by "there is no Turing machine that can decide whether a given input program halts". Didn't my computer (Turing machine) literally just "decided" whether the program halts by giving me the answer after running the program? $\endgroup$ Commented Jul 4, 2021 at 22:09
  • 2
    $\begingroup$ You just did not do that for all possible input programs. There is no (fixed) Turing machine that correctly decides whether an input program halts for any possible input program. In fact, if your implementation was powerful enough to handle general javascript programs you could retrace the proof of undecidability of the halting problem. Create a program $P(x)$ that uses your predictor to detect whether an input program $x$ halts when it receives input $x$. If the answer is affirmative, enter into an infinite loop, otherwise return. Invoke $P$ choosing $x$ as $P$ itself. Does $P(x)$ halt? $\endgroup$
    – Steven
    Commented Jul 4, 2021 at 22:15
  • $\begingroup$ @Steven well, the program you described will not halt, since it has an infinite loop. That's my point. Turing assumes you have to run the program to determine whether it halts, he basically creates a paradox by using a wrong premise. And I'm saying you don't need to run your program and lead it into an infinite loop, you can just evaluate all the program statements and analyze it without even running it to determine whether it halts. the fact that it would be difficult to create such an advanced analyzer doesn't mean it's impossible $\endgroup$ Commented Jul 4, 2021 at 22:23
  • 6
    $\begingroup$ Have you read the standard proof that the halting problem is not computable? It doesn't "assume the only way to check whether a program halts is to run it" as you claim. $\endgroup$ Commented Jul 5, 2021 at 5:28

2 Answers 2

3
$\begingroup$

Please feed this program (pseudo-code) into yours.

for every integer n > 3:
  has_solution := false
  for every prime p < 2*n:
    if (2*n - p) is a prime:
      has_solution := true
      break from inner loop
  if not has_solution:
    halt

Congratulations! You have solved the Goldbach's conjecture!

A step-by-step analysis of your program when it is fed with my program should reveal the problem.


To make it clear, it seems that you solved a subset of the halting problem, and assumed that it can theoretically be extended to the general case. It cannot. In my program, the has_solution variable changes very unpredictably, and it is very hard for you to write a program that analyzes this change.

Indeed, Turing's proof constructed a program specifically aimed against a putative "solution" of the halting problem, in a similar spirit. So that any "solution" will have a weak point where it cannot accurately get the result.

$\endgroup$
2
$\begingroup$

The halting problem asks whether a particular Turing Machine will halt if given a particular input. If you don't consider the input, you can't claim to solve the halting problem; a given program might halt for some inputs and not for others.

You can substitute the input with a static initialisation without altering the sense of this objection. It's not sufficient to just detect the presence of an infinite loop. That says nothing, because for particular inputs, possibly even all inputs, the loop may never even happen.

Consider the following program (which assumes the existence of an arbitrary-precision integer arithmetic library) for deciding whether there is some $n>7$ such that $n!+1$ is a perfect square (the so-called problem of Brocard). (Here, I've hard-coded the minimum value rather than taking it as an input.)

let n_factorial = 40320
let n = 8
while (!is_perfect_square(n_factorial + 1)) {
    n += 1
    n_factorial *= n
}

Can your program prove that it never halts? How?

$\endgroup$
2
  • $\begingroup$ The input part can actually be reduced away: simply imagine a subroutine eval(prog, input). This program emulates the behavior of prog when fed the input input, but takes no input itself. $\endgroup$
    – Trebor
    Commented Jul 5, 2021 at 4:02
  • $\begingroup$ @Trebor: sure, but it doesn't make any difference. Either way, the static analysis has to take it into account. The mere possibility of an endless loop is not sufficient to declare that the program won't halt. $\endgroup$
    – rici
    Commented Jul 5, 2021 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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