Software Development

Some functions may halt with some parameters and not halt with others...

This is quite true and the basis of my argument. I take it one step further in that we know with 100% certainty that a function that takes another function as input will never halt. In fact, it's an invalid program because there is nothing to act upon. The result is simply a compound function. But in the Halting proof, they use this incomplete program to "prove" that it's impossible to tell if a program halts or not which is a completely bogus conclusion.

What does "while(f()!=0);" actually mean?

It means exactly what it says. This is standard C or C++. I believe it's common in other languages too. It invokes function f until it gives a result of 0.

Think of it this way. Function f can be substituted by a value. We just don't know which one.

Is it 0? We don't know. It's undecidable.

So the halting problem uses this EXACT property of undecidability to "prove" that it's undecidable to know if a function halts or not. Again, it's bogus. The program is incomplete.

However, the Oracle always requires a parameter. Would you please sort these things out first?

This is exactly my argument. You are quite correct. However, I'd ask the people who came up with the halting proof to sort these things out. What they are doing is using a function as input to program P, and then saying that it's undecidable for the Oracle to say if the program P halts or not. Well, the program is incomplete. It still has no input that can be acted upon in the way of which we are asking the Oracle.

Do you now see how providing a function as input is the same as providing no input at all? Two functions together is simply one larger function. There is nothing to act upon. So that's why I used f(). It has no argument. It's simpler and more direct to see this way if I'm point blank about it. One function, two functions, a million functions... they are all equivalent to a single function with no arguments, hence f(). I then go on to the next step of showing how providing inputs doesn't necessarily mean you've given the function anything to act upon. The halting proof is nothing more than creating an incomplete program and then saying the Oracle cannot tell if it halts or not. Well, DUH! The Oracle has no obligation to provide an answer for incomplete programs.

Oh, almost forgot. I'm not the one allowing functions as values. It's required by the Halting Problem. However, if the second input to the Oracle was not allowed to be a function, the halting proof would fail. That should be something of real concern, but it's always brushed aside with some hand waving.

A function must always take a parameter and cannot have side-effects.

Maybe in the functional paradigm, but there is no such requirement in a Turing Machine.

BTW, if it were possible, I would 100% agree with you on your premise because then the halting proof would fail instantly. Ironically, your quote applied to the second input to the Oracle is precisely why the halting proof fails. Even though the input is specified, it cannot be acted upon (resulting in a situation much like your example, causing an equivalent function with no input). Unfortunately, the specifications of the Oracle says that it must act on the input, therefore creating a contradiction. But it's a bogus conclusion. The contradiction stems from the invalid program.

I think, the point of the halting problem is not, that you cannot decide, whether a partial program halts, but whether a complete one halts.

Exactly! But the halting proof only provides a partial program. Not a complete one. And this is one of my points that the Oracle need not give a correct result (or any result at all) for an incomplete input program.

If you have an arbitrary program and provide it all parameters it needs to run, can we then know, whether it will terminate?

Yes! This is the proper question.

The halting problem proofs say "no".

It does no such thing because the halting proof only provide an incomplete program in order to produce the contradiction. Therefore, the halting proofs must be rejected.

BTW, did you know that you only need ONE instruction that operates on data? All remaining instructions are used for control statements. That ONE operation is either NAND or NOR. Use either one (and only one) and you'll achieve Turing Completeness.

Now, both NAND and NOR have two inputs. These only take raw data. Either 1 or 0. Nothing else. And unless you're building a compiler (or similar program), it cannot take a function representation as input either. So look in the deceiver program and find out where the two RAW input values are. The same input can be duplicated to produce a simple NOT operation I suppose. So where is that RAW value in the deceiver? It cannot come from the Oracle because the Oracle produces its output based on the input. Look at its input and you only find more functions. Again, look at their input and you'll loop back to the Oracle. There is NO RAW VALUE ANYWHERE.

IOW, there is never any input. NEVER. It's an incomplete program that cannot possibly execute. We don't even need to attempt to execute it. There is no RAW data anywhere. Without anything acting on raw data, all you have are control statements. If any of these act on RAW data (like conditional jumps, if statements, loops, etc.) then you have an invalid program because you have nothing to act upon. The condition in the deceiver program is what causes the program to be invalid.

This means that program P never acts on its input and neither can the Oracle. Multiple functions simply reduce to a single compound function g. So passing two functions to the Oracle should not be allowed.

True that sometimes you can tell if a program halts or not without having to look at said program's input. But as I've said in my paper, this is not always possible. And when it's not, you need that input to eventually lead to RAW data. The deceiver program does not satisfy this requirement and as such is incomplete.

Look at the halting proof again and force the program to be complete. Force the input I to be data and not a function. You will soon realize that it's impossible for the halting proof to hold up.

The function in the proof is not partial. The first parameter is the function as source code. The second parameter is any other explicit value.

Go read the proof again. The second parameter is not an explicit value. It's a function. This makes the first function a partial program since it has nothing to operate on. The Oracle doesn't even enter the picture.

What you fail to understand with your hardware analogy is that you *can* produce a circuit that can take as its input a representation of circuits and make decisions about them.

Logic gates only take voltages. And even if you consider what happens at a higher level, what you prove on a representation is not necessarily true on the principal.

For example, just because I can prove array indexes are unique, it doesn't mean the values contained therein are unique.

Then I called the function and it ran. So your assertion that a function cannot take as an argument another function and yet be a whole function is demonstrably wrong.

You haven't demonstrated anything. All you've done is confuse composability with compositionality.

It is this layer of abstraction - a function looking at a *representation* of another function - that makes the Halting Problem proof work

A representation is just that, a representation. It's not the function itself. What is proven about the representation is not necessarilly true of the principal. So no, the representation is most definitely not what makes the proof work.

FYI, my paper shows what you can determine from function representations alone. So it doesn't matter if you think functions can be represented with raw data. There's only so much you can determine.

The proof says assuming that there exists a function H(f,i), that gives a *correct answer* for all functions f and all inputs i, then it is possible to construct a function T(f) that exhibits the opposite behavior of "f" when called with "f" as a parameter. But the behavior of T(T) is inconsistent with itself; according to the definition of T, if T(T) runs forever, it halts, and if it halts, it runs forever. Thus T cannot exist, because H cannot exist.

What you forget is that H is only required to provide a *correct answer* if you provide an input i to the function f. Without such an input, then H cannot possibly provide a *correct answer*. So the result of the halting proof only shows that input i has not been provided.

A function is not an input unless you are writing a compiler (or something similar to it). The deceiver program is not a compiler. It INVOKES its input program. So the representation is not used as data. If the function is not data, then where is the data needed for the comparison? It's simply not there.

One last thing is that a compound function is still just a function. There's no input there and doesn't satisfy the requirement stated by the halting problem. So any "proof" based on T(T) is hereby rejected since you've only provided the equivalent of a single function. There is no opposite action since there is no action to begin with.

The point of the halting problem is there is no generic way to see if a program runs forever, except by running it.

This is incorrect. Everyone already agrees on this point, so I won't discuss it here.

In short, virtually every single statement you've said in your comment is incorrect, or unrelated to the topic.

BTW, did you know that you don't even need the deceiver program? An enabler program (one that does EXACTLY what the Oracle says) is likewise indeterminate. So doing the opposite or doing the same thing is completely arbitrary. And if it's arbitrary, then it cannot possibly be a proof by contradiction.

> What you forget is that H is only required to provide a *correct answer* if you provide an input i to the function f.

The arbitrary-argument halting problem is easy to prove unsolvable if it is known that the single-argument halting problem is unsolvable. It is trivially shown that a multiple-argument or zero-argument function that calls a single-argument function with one of your inputs, or even just zero, can be constructed.

The halting problem isn't asking if you can construct something (composability), it's asking if you can determine behaviour (compositionality). For this, it needs at least one piece of data (if the only action is passing data along or inverting it.) In most cases, like the deceiver program, the equality operation requires two pieces of information and only one is ever given thereby making any assessment on compositionality impossible.

It's not that the Oracle can't exist. It's that the program is invalid. The Oracle need not give a correct answer (or any answer at all) on invalid programs. But the halting problem proof incorrectly uses this fact to show a bogus contradiction.

And a logic gate is not turing complete.

If you're allowed to connect them together as you wish, they are.

An equivalent problem for digital logic is this: Given an arbitrary logic circuit, electrical waveform, and internal digital state, can you devise a circuit (or equivalently, program) that always tells you, within a finite amount of time and with certainty, whether or not that circuit will reach that state?

Will *what* reach a certain state? And finite time? Time has no basis in the halting problem.

This is a totally specious argument. A function's representation is not arbitrarily detached from the function the way array indices are detached from what they point to.

Of course they are arbitrarily detached from the function. What does 1 mean? It could mean addition. It could mean subtraction. It could mean anything at all. It's 100% arbitrary.

My goodness, if this part isn't clear, then I'm afraid you've been too caught up in the awesomeness of your own hand waving.

> what you prove on a representation is not necessarily true on the principal.

But the halting problem isn't asking about a problem in principal, it's asking about the code itself.

If you can't understand that the halting problem is asking about a runtime property of the function and not a property of the representation, which can neither execute nor not execute, then I'm afraid I can't help you.

Do you understand that a representation cannot execute. It cannot halt. It cannot not halt. It just is. In fact, this is why the halting problem proof is flawed. You're wording the same flaw in many different ways. But it's all the same thing. I'm ok with people saying that "you're executing X code", but when dealing with proofs, I will strongly object to this usage. Only the machine may execute. Never the code.

Also, I'm not sure you understand that the term "principal" is used in a representation vs. principal relationship. In contract law, it'd be agent vs. principal where the agent acts in the place of the principal (aka another person or company) in certain areas.

When you're talking about code to be read by an interpreter or CPU and executed, a function is completely inseparable from its code.

Not entirely true, but it's nice to see you placing limits on how the code is used. Good. This is the first thing I've seen you do that shows any inkling of heading in the right direction. Perhaps you can now see that only certain properties, and only in certain cases, do the properties of the function itself become apparent by its representation. But you've yet to understand that all other properties of the representation are not reflected by the function. And that in all other cases, even the properties that WERE reflected by the function, those properties no longer hold.

Now then. What is a function? It's an action. Actions are NOT tangible. Can you write down the words "go to the store"? Of course. But the wording and the action are two different things. I can prove that "go to the store" has 4 words. But does the action have 4 words? No. It doesn't even make sense to say such a thing. So what is true with the representation is not necessarily true of the action/function. Do you finally understand this? It's not rocket science.

The representation indicates very specific properties about the function with an understanding between the machine that performs the actions and said representation. And that's it. Any other properties of the representation are NOT true of the function. For example, a representation has a length, but a function does not. In my paper, I show some properties that can be ascertained from the representation alone, and some that can't.

I hope this clears up any misunderstanding you may have had.

The entire basis of turing completeness is representation, since without representation of a function, you cannot emulate another turing complete language and cannot be turing complete.

This is an ambiguous statement. I can use numbers to represent a function, but it doesn't mean I can use all properties of the representation as properties of the function.

>FYI, my paper shows what you can determine from function representations alone. So it doesn't matter if you think functions can be represented with raw data. There's only so much you can determine.

Congratulations! You've done what hundreds years of research into computability hasn't fully answered yet! In one paper, you've fully described everything that can possibly be done with code-as-data!

Once again you miss the point. Yes, I *get* that there's only so much you can tell just by looking at the code and not running it.

Which one is it then? I said there's only so much you can do with representation and you say this hasn't been done in 100 years and then you agree with me? How does that work?

BTW, look up NAND and NOR logic gates. It's been established for quite a few years that these are universal gates.

And besides, it's not a matter of what I think. Turing completeness proves a function can be represented with raw data by its own definition. It says you can write a Lisp interpreter in Lisp and hand it that "raw data" and have it behave exactly like lisp.

But you miss the point that the machine only uses a previously agreed upon relationship between the symbols and the actions, nothing more. The halting proof goes well beyond this relationship and uses properties of numbers of which the function does not partake.

>>The point of the halting problem is there is no generic way to see if a program runs forever, except by running it.
>This is incorrect. Everyone already agrees on this point, so I won't discuss it here.

On the contrary, it is the fundamental motive behind the halting problem. It is trivial to see if a program halts by running it to see. Didn't return yet? Wait longer. The halting problem asks if there is a way to generically reason about code to determine if it halts *without running it*.

Such a program would have extraordinary consequences to number theory. Any standing problem that asks whether a certain class of numbers (like primes or perfect numbers) is finite or not would instantly succumb to H, because you could just write a program that checks every integer for that property and run it through H.

If running it was enough, there'd be no need for the halting problem since it'd already be a resolved problem. If you can find an answer by whatever means, then you can write a program that can do the same thing. Sorry, try again. And to repeat myself, this is already accepted by everyone. So don't bother trying to convince me. Try convincing others and then we'll talk.

About the consequences of the Oracle's existence, you're wasting time and effort because I'm not arguing if the Oracle can exist or not. I'm only saying all the current halting problem proofs are incorrect.

I'm going to requote this little gem.

*without running it*

I'm not saying either way whether or not the Oracle should run the program, but if you're making the argument, please show me in the halting problem where this is a requirement? I think you'll be surprised. No need for debates. Just quote the part of the halting problem that states this as a requirement. If you can answer that, we'll move on from there. Otherwise, there is no point in talking about fiction.

> In short, virtually every single statement you've said in your comment is incorrect, or unrelated to the topic.

Dismissing your detractors like this is a good way to not get taken seriously.

Point taken, but you're gonna have to start saying something that's actually correct soon, otherwise there'll be no need to be taken seriously be people who don't understand the topic.

> An enabler program (one that does EXACTLY what the Oracle says) is likewise indeterminate.

Absolutely not. It is the behavior of T that is indeterminate, not its output, and then if and only if H is correct in all cases.

H is correct with respect to T since it does exactly what H says.
And T is indeterminate because we don't know if it will halt or not.

If you can't show how those statements are false, you're going to have to accept that the enabler program is just as "good" as the deceiver program for a halting problem proof. And once you accept that, then you have to dismiss the halting proof as a proof by contradiction since doing the same thing or doing the opposite has no relevance to the conclusion of the proof.

T does not run itself, because H does not run T.

First, no one ever said H runs T.
Second, H can do what it wants as long as it returns a result on valid input.
Third, T must still be runnable otherwise there is no point in asking about a runtime feature.

To suggest that H can't exist because no function can take a function as an argument is ludicrous. I can very easily write a function that would examine another function and check for unbounded loops and recursion and return false if they exist and true otherwise.

I talk about this in my paper. But you cannot determine every behaviour. If the program in question acts upon inputs, then you must have those inputs. And if you only provide functions as inputs, then you can't determine the behaviour since there is not sufficient data to have any kind of compositionality.

Remember, we're not talking about specific cases, but ALL of them. So only providing functions will only provide you with so much information on behaviour.

That is what the halting problem proof says: that every program designed to determine, ahead of time, whether some code terminates (or again equivalently, whether some line of code will be executed), will give at least some wrong answers.

It does no such thing because there is insufficient data to have compositionality between any two data items as there is only ever one piece of data for the comparison. The Oracle has no obligation to provide a correct answer when there is no compositionality.

> A function is not an input unless you are writing a compiler (or something similar to it).

This is a completely arbitrary restriction that you impose. I showed you why it was false: cast the function pointer to a char* and print out its machine code.

It is not arbitrary. Converting a program to another format doesn't require the raw input data. But analyzing the behaviour of the program CAN require the inputs to that program. This is a very real difference. It's not something I made up. In fact, it's why the halting problem requires an input in the first place.

Besides, the deceiver program doesn't care about the source code at all. All it does is invoke the function.

> The deceiver program is not a compiler. It INVOKES its input program.

No, it does not. It calls H on it. And H does not invoke it, it reasons about it and returns an answer. That is what H is supposed to do, and the existence of T given H's existence shows that H cannot exist.

Let me quote this again... It's too good.

> It INVOKES its input program.

No, it does not. It calls H on it.

A: It's red.
B: No, it's red.
A: I already said it was red.
B: No, you said it's red. That's wrong. It was in fact red.

HAHAHA!!!

Sorry, but this is funny as hell.

>So the representation is not used as data.

See above. It passes the representation to H which does some internal reasoning on it and returns an answer. Once again, it is very easy to write H such that it is partially correct! But by all means, go on suggesting that H can't exist because it can't take a function as a parameter. It won't make it true.

I'm talking about the DECEIVER not using the representation as data!!! Not the Oracle!

>One last thing is that a compound function is still just a function. There's no input there and doesn't satisfy the requirement stated by the halting problem.

You're still missing the point. Functions and data are all the same because a faithful representation of that function as data is possible due to turing completeness. You can't have turing completeness without representation as data.

Functions and data are NOT the same. They can NEVER be the same. Prove to me that they are if you wish to use that argument. It's patently absurd to think that a representation is the same as the principal. If they were the same, then you wouldn't need a representation. You could just use the original.

void T(void (*func)(void*)) {
if(H(func,func)) for(;;);
}

How is T not invoking H here?

By your assertion, this code snippet cannot exist!

I never said that.

If instead the body of H invokes T, it causes an infinite loop which violates the halting problem which requires H never to halt.

No one ever said it invokes T. You were the one who was mixed up about that. I never even think of executing the input programs, ever! I'm not sure why you can't see my paper, but if you'd read it, you would see that I've already discussed all of this.

If H calls T in a thread and kills it and returns false if it hasn't halted in 10 seconds, or if H looks at the assembly code pointed to by T and makes an educated guess, it will be incorrect some of the time, which also violates the halting problem.

Not even wrong. This makes no sense at all why the Oracle would work that way. And the last part is simply handwaving.

The halting problem, by contrast, asks if there is a function that always halts and always returns a correct answer. In other words, is there some way the body of H can reason about the code to the function passed in and return a correct answer every time in finite time? The existence of T proves that it can't.

Again, handwaving. Why does the existence of T prove this? I've shown that the result of the halting problem proof shows that there is no input.

Until you accept the importance of representation, and its inextricability from the code itself, to the halting problem, and realize that H does not invoke the solution but analyzes it, you will continue to miss the point of the halting problem (and turing completeness in general).

First, if the representation and the principal are the same, then remove the representation all together since you can use the principal directly.

Second, I've never said H invokes T. You're the one who got confused about that. In fact, my paper explicitly says what you can determine about function representations BEFORE ever thinking of executing any function (as it relates to halting and not halting). Read up on compositionality if you want more details. Hopefully, you'd more readily accept information that comes from a different source.

I have no other way to say it, but you only provide handwaving. You have provided nothing other than personal belief, or repeated things you've seen and read. Demonstrate WHY what you say is true instead of just stating it. I've demonstrated how representations have different properties than the principal with "go to the store" example. This is called a counterexample and is good enough to disprove your argument that the representation is the same as the principal. Yet, how did you respond the first time around with my array counterexample?

With this!

This is a totally specious argument.

How? Why? You say nothing more. You only state your beliefs when I've shown a counterexamples.

You did try to provide an example with some code. Unfortunately, you completely misread what I was saying.

Then you go against well known and accepted facts. If you have an argument for this, then please state them. I'm using what's in common agreement.

Here are two instances where you did this.

1. You disagreed with the equivalence of NAND or NOR networks with Turing Machines even though the latter is built with the former (other than the infinite tape/memory). And also that it's been known for a very long time that NAND and NOR gates are universal.

2. You incorrectly believe that "it is trivial to see if a program halts by running it to see."

The second one is my personal favourite.

I'm in 100% agreement with the rest of the computing community when it comes to those two points. So please don't think that these two points are my arguments alone. They are accepted by the entire computing community. Not only that, I've explained WHY you were incorrect in my response.

I just want to recap a few points since they seem to be repeated by a lot of people (and not just in this thread). I don't know why they repeat them, but it gets rather tiring.

1. No one is running the input program (or second input argument) to the Oracle.
2. No one is arguing that the Oracle exists (or doesn't exist).

I may add more points as we go along, but these arguments need not be repeated since I agree with them.

If you have an argument, it should be something other than the ones listed above. Please resist the urge to repeat them. They are not arguments in your favour.

Here is a followup on this topic for those interested.

Halting Problem: Composability and Compositionality

What he explained was not just correct, but also written in a concise non-superficial way and without getting too personal.

I hope this is a joke. In the future, please try to avoid handwaving arguments because I don't think you understand what you are agreeing with.

For example, do you believe that running the program is enough to tell if it halts or not? And that this works for ALL programs? C'mon!

Regarding Vorlath's arguments: Of course representation is arbitrary. What gives a representation its meaning is some set of rules, a calculus, that tells how to transform one set of symbols into another.

This is correct, which is more than I can say for any argument presented by the anonymous posts. But the halting problem proofs disregard those rules you mention.

So with respect to a specific calculus, functions do indeed have a representation.

No one said functions can't have a representation.

BTW, since you've thankfully stated that you have a representation, what EXACTLY does it represent? The answer to this question completely destroys the Halting Problem Proofs.

I will state again. A representation is meant to STAND IN for the principal. But they are not the same and they do not share all their properties, otherwise you would have the original. So any halting proof based on properties of the representation without regard to the function itself must fail.

Here is one critical difference, code does not execute, ever. As I've said before, I have no problem saying "This code is executing" when speaking in general about programming. But when it comes to proofs, this is unacceptable because only the machine can execute or perform any action. Glyphs, symbols or whatever else have never performed any action in the history of humanity.

From your post, it's obvious that you do not understand this fundamental rule.

Vorlath seems to assume that functions are god-given black-boxes that are not tangible.

Quite right, though I could have done without the god-given black box part. Point is that functions are NOT tangible, only their representations are. I've explained this before. Execution is an ACTION! Actions are not tangible. And as I've said before, you can have a piece of paper that says "go to the store", but the action of going to the store is a different beast all together.

The halting problem indirectly proves that the oracle is not computable.

Handwaving.

Here's the definition of representation.

rep·re·sen·ta·tion (rpr-zn-tshn, -zn-)
n.
3. The state or condition of serving as an official delegate, agent, or spokesperson.

It's in the definition that agent != principal. With a Turing Machine, a function is the principal and the symbols of your code are the agent.

Agent != Principal
Symbols != Function

Doesn't get simpler than that.

However, perhaps the person who posted under the name "A" would like to contradict this definition. Perhaps you would like to contact the Houghton Mifflin Company and tell them that The American Heritage® Dictionary of the English Language, Fourth Edition is incorrect and that you'd like to update one of the entries.

If I sound frustrated sometimes is that people go against some of the most basic principles. Not just basic, but so fundamental that I don't understand what frame of mind would cause one to think that a representation is the same as what it represents for all properties.

From your comment, I believe you are trying to show how one representation can be equivalent to "something else". If I'm mistaken, then please correct me.

And you also happen to have some rules...

Ah, but here we dance around the problem. A representation will have rules that apply to the principal (for letting the machine determine the properties of said principal) as well as other rules that do not apply to the principal. The Halting Problem Proof does not restrict itself to those rules that apply to the principal.

wouldn't you say, that IN THIS CONTEXT the glyphs are equivalent (not equal, but equivalent) to the successor function?

First, I'm not sure you understand that the glyphs would likewise be representations. So I'm not sure why you would be appending numbers to glyphs.

Second, it would definitely NOT be equivalent to the successor function since there are many representations that are equivalent to each other and some that produce IDENTICAL results unlike the number system, hence you would need a different set of rules.

Third, if you're trying to map the glyphs to a sequential series of numbers (if I understand you correctly), then you still have one set of rules which are not exclusively used by the Halting Problem Proofs.

Why shouldn't I then be able to reason about the behaviour of the function within the context of my system?

If you were to restrict yourself to the set of rules that apply to the principal/functions and it was the behaviour of you as a human or of some machine that does performs the action, YES!!! By all means, go for it. But the Halting Problem Proofs do not do this. They use the rules that apply to numbers without regard to the rules that apply between symbols and their interpretation by the machine.

As an example, the number 1001 can be interpreted as one thousand and one OR as the number nine in binary. I can show a contradiction here. This is essentially what the Halting Problem Proof does. Am I allowed to treat one representation as another if I want? Sure. But any resulting contradiction is bogus since it no longer follows any rules that apply to the original principal. As an aside, this is also exactly what Cantor's diagonal argument does.