Is There Anything That Cannot Be Programmed?

Status
Not open for further replies.
TruthSeeker

TruthSeeker

Fancy Virtual Reality Monkey
Valued Senior Member
Simple question- can every single process in the universe be modeled into a computer program?

Example... if you know all the variables, can you simulate the lifetime of a star?
 
"if you know all the variables"

Therein lies the problem. You can *model* it, but until we figure out how to collapse the uncertainty principle (if it's even possible), you can't know all the variables.
 
It would take all that is in the universe to make all the variables. Then, we would just be modeling the computer.However, we'll need all these variables PLUS MORE to make the program (functions and such).

So no. At best we will only ever be able to model in the universe in general.
 
What you are talking about is a branch of computer science called computability. For a long time it was assumed that all problems were solvable. That is, although we may not KNOW the solution, one MUST exist. The cannonical example of why this is NOT true is called the Halting problem. Usually the proof involves using a Turing machine as a model of computation (but actually using a diagonalization proof, you can prove it for ANY model of computation).

Halting problem goes something like this: Can you construct a program HALT, which will read in another program P, and an input X and tell me whether or not that program P will ever stop when run with the input X?

The answer is no, you cannot, at least not something that works for ALL possible programs. Let us assume we have a Turing machine called HALT which can do what we say. This Turing machine takes in P and X, and returns True if P halts on X, and False otherwise. In this case, P is simply a natural number representation of the program. We can consider it an index.

Now, since we are assuming that HALT exists (although we are making no assumptions about how it works). We can then construct a different machine called DISAGREE which takes in just an input Y. DISAGREE(Y) will return True if HALT(Y,Y) is False, otherwise DISAGREE will never return and will loop forever.

As an input, let us use the index of DISAGREE (since it is a program, it must have an index) and called this index d. We then can call DISAGREE(d). DISAGREE(d) will return True if and only if HALT(d,d) returns False and HALT(d,d) returns False if and only if program d, when run on input d, never halts, but this implies that DISAGREE(d) never halts. This DISAGREE(d) halting implies that DISAGREE(d) does not halt. This is a logical contradiction, which means our original assumption that HALT can exist must be false. Therefore, no program can exist which solves the Halting problem.

----

Thats pretty much from memory, so please point out any minor mistakes. Its actually now possible, using HALT, to prove lots of other problems as unsolvable using reduction. HALT is a problem in the class RE = recursively enumerable, non-recursive. It is considered semi-decidable, since given any arbitrary program an input, if it DOES halt, we can tell you (since we can just run the program and tell you if it halts). If it does NOT halt though, we can never tell you since it will just run forever.

There are actually harder problems that are not even semi-decidable, they are in a class called non-recursively enumerable. The cannonical problem for this is called the Universal Halting problem, which asks, given a program P, does this program halt on all possible input? Which essentially asks the question, is program P an algorithm? (since all algorithms are programs, but not all programs are algorithms). Even if we DO give you an algorithm as your input, you cannot possibly test all input, and therefore you cannot even reply yes for a yes case. Thus it is not semi-decidable (this is a reasoning, not a proof).

-AntonK
 
Wow. I'm lost. :D

Maybe you should give an example of a problem that cannot be solved... :D

:)
 
Excellent post, AntonK. I would also like to add that variables are abstractions of reality. It requires translation of phenomenon with no clear boundry into digital symbols, and something is always lost.
 
TruthSeeker said:
Wow. I'm lost. :D

Maybe you should give an example of a problem that cannot be solved... :D

:)
Click to expand...

The Halting problem is an example of a problem which cannot be solved. Take a look at The Wikipedia Entry for the Halting problem for more information about it. Its the canonical undecidable problem, but the truth is there is a whole plethora of interesting undecidable problems.

-AntonK
 
spidergoat said:
Excellent post, AntonK. I would also like to add that variables are abstractions of reality. It requires translation of phenomenon with no clear boundry into digital symbols, and something is always lost.
Click to expand...

I would argue that is not correct. Programs, Turing Machines, Recursive functions, rewriting systems, etc. are all models of computation. They have all been proven to be complete (that is, nothing can be calculated that cannot be proven to be calcualted with one of these models). As a MODEL of computation they are inherently more powerful. While I can construct a Turing machine with inifinte tape, I cannot ever actually buid it. While I can use recursive functions which can recurse to infinite depth, I could build no actual machine to do it.

Arguing that there is a translation into "digital symbols" is also incorrect. We are talking about abstract models of computation here. There is no actual hardware involved. We are simply looking at the most RAW form of computation. What CAN be computed and what CANNOT be computed (ever... by any machine possible). That is what makes the field so interesting.

-AntonK
 
Maybe you should give an example of a problem that cannot be solved...
Click to expand...

Antonk's post reminded me of another example.

Let say you wanted to write a program that would verify the correctness of other programs by getting source code as input.

While some aspects of that assignment are possible (such as syntax checking), you can never satisfy all requirements, for one simple reason - you can not feed the program you wrote itself as input, and expect a valid answer.

If your program is right, then the program will validate itself as right. But if the program is wrong, it may still validate itself as right, because the validation process is flawed.

Thus, you can never program something that validates its own correctness.
 
river-wind said:
Antonk's post reminded me of another example.

Let say you wanted to write a program that would verify the correctness of other programs by getting source code as input.

While some aspects of that assignment are possible (such as syntax checking), you can never satisfy all requirements, for one simple reason - you can not feed the program you wrote itself as input, and expect a valid answer.

If your program is right, then the program will validate itself as right. But if the program is wrong, it may still validate itself as right, because the validation process is flawed.

Thus, you can never program something that validates its own correctness.
Click to expand...

This is similar to the proof that mathematics cannot be proved to be true. The axioms cannot be proven.
 
What about the butterfly effect? To compute the outcome, for instance of a particular state of the weather, your initial model would require infinite resolution, because the tiniest difference between your model and reality could result in macro-changes to the outcome. Since the resolution of any model cannot be infinite, we can never simulate (calculate) reality with 100% accuracy, and the model would get progressively less accurate at larger timescales.
 
spidergoat said:
What about the butterfly effect? To compute the outcome, for instance of a particular state of the weather, your initial model would require infinite resolution, because the tiniest difference between your model and reality could result in macro-changes to the outcome. Since the resolution of any model cannot be infinite, we can never simulate (calculate) reality with 100% accuracy, and the model would get progressively less accurate at larger timescales.
Click to expand...

What you are talking about is more like intractability. For instance, I can PROVE to you that a machine exists which can calculate the weather. I call this computer "Earth". Simlpy let it run, then interpret the output. All physical processes can be computed, as long as you do not take a limited view of what "computing" is. This is why when we talk about undecidability, we talk about abstract computational devices as opposed to a specific computational device.

-AntonK
 
Given the same inputs (state of the Earth) yes. I can guarantee it. Undecidability has less to do with whether or not you can get the right inputs, as it does with GIVEN the right inputs, is it even possible to calculate it? And the answer is yes, given the right inputs, physics calculations are easy

-AntonK
 
river-wind said:
"if you know all the variables"

Therein lies the problem. You can *model* it, but until we figure out how to collapse the uncertainty principle (if it's even possible), you can't know all the variables.
Click to expand...

and we come back to my initial response. You make a good point about the abstraction of "computing" for this types of discussions, but I would be hesitant to say that the Earth's calculation method is purely predictable and reproducable.
 
AntonK said:
Given the same inputs (state of the Earth) yes. I can guarantee it. Undecidability has less to do with whether or not you can get the right inputs, as it does with GIVEN the right inputs, is it even possible to calculate it? And the answer is yes, given the right inputs, physics calculations are easy

-AntonK
Click to expand...

But you can never make a perfect model of reality, can you? Even theoretically. And the parts you leave out could add up to significant macro-scale effects.
 
I think from the moment you know "how" something works you can. But that's it, we don't know how everything works therefore we cannot program everything.

Even if all the variable are known that doesn't mean we know how to manipulate them in order to get the right output.
 
Last edited:
Status
Not open for further replies.
Back
Top