-2
$\begingroup$

As far as I know, the halting problem means we can't create a program that checks whether another program is stuck or halt based on given input. This means, the program expects two inputs and one boolean output.

For example in a Python language, there's program called is_halt.py expecting one input integer. Let's say the input integer is N. If 0<=N<10 then stuck, else then halt.

I tried ChatGPT which is working on soft computation.

Prompt (Input):

#I have this Python Program:

integer_input = int(input("Input an integer: "))
while integer_input >= 0 and integer_input < 10:
  print(1)
print(0)

#If I input the integer with 7 into the program, will the program halt or stuck?

Answer (Output):

The program will get stuck in an infinite loop when you input the integer 7. The loop condition while integer_input >= 0 and integer_input < 10: will always evaluate to True because 7 satisfies both conditions (7 >= 0 and 7 < 10). As a result, the print(1) statement will be executed repeatedly, and the program will not reach the print(0) statement. To avoid the infinite loop, you need to update the value of integer_input within the loop to eventually break out of it.

As you see, the ChatGPT 3.5 answer is able to check whether the program is stuck or halt based on given input.

Does it mean, the halting problem is solved by soft computation?

$\endgroup$
3
  • $\begingroup$ Also ChatGPT paid version now includes in-app Python Interpreter since it can't understand number really well, I'm wondering what the output will be if I tell it to run the program with input 7 which is stuck, I don't have paid version. $\endgroup$ Commented Jul 31, 2023 at 18:55
  • 2
    $\begingroup$ Testing ChatGPT on one example says nothing about how it works on all examples. A Hlating oracle must correctly determine halting on all programs, i.e., whichever program you give it, it returns a correct answer. $\endgroup$ Commented Jul 31, 2023 at 19:45
  • $\begingroup$ What, exactly, is "soft computation" and why might it be expected to have different fundamental limits than computation has? $\endgroup$
    – kaya3
    Commented Aug 1, 2023 at 14:12

4 Answers 4

2
$\begingroup$

As far as I know, the halting problem means we can't create a program that checks whether another program is stuck or halt based on given input.

No, the Halting Problem means that we can't create a program that checks for all possible programs and all possible inputs whether the program will terminate for that input.

You have found a program which can check that for one program and one input. I am sure, ChatGPT can do that for many programs and many inputs. But that's not enough.

You have to test ChatGPT with every possible program. That includes every program that has ever been written in the entire history of humankind. And every program that will be written for all eternity. It even includes programs that have never been written and will never be written, but could theoretically be written. It includes the program I just made up in my head and have already forgotten again.

And you have to test every possible program with every possible input.

There are many programs for which it is trivial to decide whether they halt or not. As mentioned in another answer, programs which contain no loops will always halt. Programs which contain only bounded loops will always halt. Programs with structural recursion where the structure always gets "smaller" will always halt. For programs with trivial infinite loops, it is trivial to decide whether they will halt.

There are many tools which check whether programs halt. Microsoft Research's Terminator is a well-known tool for termination checking. A variant of it is actually used to check termination of Windows Drivers to make sure that Windows Drivers cannot freeze the kernel.

But all of these tools and all of these tricks can only decide termination for some programs. Not all of them.

Terminator is proven to be sound, which means that when it says a program will halt, then the program will definitely halt. However, Terminator is not complete, meaning there are programs which halt for which Terminator cannot decide that they halt.

In many use cases, this is an acceptable trade-off: your goal is to prevent Windows Drivers from running into an infinite loop. As long as you can guarantee that you don't allow a driver with an infinite loop, then it is okay if you occasionally disallow a driver which doesn't have an infinite loop. The cost of a false negative is that the developer has to change their code so that Terminator can understand it. The cost of a false positive is a potential Windows Bluescreen. You'd much rather have the former than the latter.

$\endgroup$
1
  • $\begingroup$ this isn't quite true. you can only treat programs given input of 0 (since a turing machine can construct an input). you also probably don't have to test every program, just all up to a certain length (the length will depend on choice of axioms but will be relatively small for any reasonable choice) $\endgroup$ Commented Aug 2, 2023 at 3:51
4
$\begingroup$

No. ChatGPT is still just a program, although a rather large one.

$\endgroup$
2
  • $\begingroup$ If you consider that the training set does not belong to the program, I guess that the program is relatively tiny. $\endgroup$
    – user16034
    Commented Aug 1, 2023 at 14:03
  • $\begingroup$ The training set is not part of the program, but the resulting neural network is, and it's pretty large from what I hear. $\endgroup$ Commented Aug 1, 2023 at 21:52
3
$\begingroup$

The halting problem does not mean that it is impossible to tell if a particular program halts or not. For example, any loop-less program will terminate, and it is a very easy matter to check the absence of loops. The halting problem says that no algorithm can work for any program.

A human could do better than an algorithm on some programs because he has more creativity and more freedom to "change the rules", so the day IA becomes intelligent (if ever ?), this might be the case as well.

Anyway, a human can be stuck on difficult problems. E.g. the Syracuse conjecture. And undecidable problems remain out of reach.

$\endgroup$
-1
$\begingroup$

One common misconception about the halting problem is that it is totally possible to make a program that will determine whether some (most?) programs halt. However if you give ChatGPT (or any other program) harder examples things will inevitably break down very quickly.

$\endgroup$
1
  • $\begingroup$ or any human, I guess $\endgroup$
    – user16034
    Commented Aug 1, 2023 at 14:29

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.