The Halting Problem Problem

[j_j]

@Corvus

But you are not being practical or realistic in your statement. No one writes codes of billions of lines alone, or tries to debug large programs like that oneself.

This sort of fits with my last response to you. You aren’t seeing what I am trying to do here.

I am “on the side” of the practical attitude.

If you don’t understand the halting problem itself, then the “problem” with this “halting problem” won’t make sense.

This topic is from theoretical computer science.

It is also, less obviously, about whether “all of mathematical reality” can be compressed into a finite amount of algorithmic information.

A “God machine” turns out to not make sense, even in principle. But I was trying to give you a sense of how weird a “God machine” would be.

A program of finite size would somehow “understand and contain” all programs, including an “infinity” of much larger programs.

[Corvus]

@j_j

This sort of fits with my last response to you. You aren’t seeing what I am trying to do here.

I can see what you doing perfectly. I think you are talking sitting on the math textbooks just passing on what the mathematicians wrote 80-90 year ago.

Now computer programming works differently. You never worry about HALT or LOOP problem in real life coding. But I can see, those simple lines in TM programs could be decision problem in logic.

If you want to just stick to the theoretical problem on decision problem in logic, we could do so. But it wouldn’t be the problem of real life.

So please explain your idea what is the point of the HALT problem, and what does it imply in logic? How could we approach the problem for resolution? Is this a problem before the program execution or after?

Could you please put down what INPUT and OUTPUT was given to the program, and how it executed the process? Or is it all in your mind?

[j_j]

@Corvus

I can see what you doing perfectly. I think you are talking sitting on the math textbooks just passing on what the mathematicians wrote 80-90 year ago.

I don’t want to offend you, but I think you are way out of your depth on this particular topic.

I don’t at all doubt your knowledge of “real world” computers and “real world” programming languages.

But this thread is about “pure math” really. The Turing machine was “dreamed up” as one way among others to make technically precise the vague notion of an algorithm. Mathematicians cared about this because they dreamed of creating a “machine” that could generate all mathematical truths without contradicting itself.

You can think of a C program that prints out, one by one, every mathematical truth expressed in symbols with an exact meaning. The program never halts because there are an infinity of truths. But the program eventually gets to each truth and prints it out. It also never contradicts itself.

Let’s say the C program is 2 million bits. Then all of mathematical reality has been compressed into 2 million bits. The structure of the prime numbers is in there. Everything. Everything “infinite” would be squeezed into the “finite.”

That would be weird.

It also looks to be impossible.

That’s the kind of thing this topic is really about.

[j_j]

@Corvus

So please explain your idea what is the point of the HALT problem, and what does it imply in logic? How could we approach the problem for resolution? Is this a problem before the program execution or after?

Could you please put down what INPUT and OUTPUT was given to the program, and how it executed the process? Or is it all in your mind?

The main idea is a program that looks at the code of other programs.

It is a program that answers questions about what other programs will do.

It’s a bit like a program that looks for bugs in other programs.

[FlannelJesus]

@Corvus

So please explain your idea what is the point of the HALT problem, and what does it imply in logic? How could we approach the problem for resolution? Is this a problem before the program execution or after?

Could you please put down what INPUT and OUTPUT was given to the program, and how it executed the process? Or is it all in your mind?

In this conversation, there’s two programs, A(x) and H(F,x)

A(x) is ANY program where you can feed a variable in (an input). You can ask this question of any program A(x) for any specific value of (x) – will the program stop if I feed in this value for x?

So I write some code, and if it’s relatively simple code I can just tell you easily, yes A(x) will stop eventually for that value of x.

Or, no, A(x) will not stop for that value of x. Most likely because the program A(x) will be stuck in some infinite loop for that value of x.

Maybe the program’s source code is simply this:

(x) → if (x == 1) return true; else (while true) console.log(x).

So if you ask, will this program stop for an input of the value 1? The answer is, YES.

If you ask, will this program stop for an input of the value 2? The answer is, NO.

H(F,x) is the second program in question. H takes two inputs. The first is another program F (maybe its source code, maybe the binary executable, idk). The second input is the x that you are going to feed into F. The H program is a program designed to take those inputs, and tell you if F will or will not stop for the input value x.

So if H is doing it’s job, then you pass in H(A, 1) and H says yes, A will stop for an input of 1.
And you pass in H(A, 2) and H says no, A will not stop for an input of 2.