Is There Anything That Cannot Be Programmed?

[AntonK]

It seems that most people now posting want to move the discussion to a more philosophical perspective. This does not interest me a great deal. However, if anyone wants to begin some investigations within the realm of mathematics and science, I suggest the look into computability theory and intractability theory.

-AntonK

 

[funkstar]

A classic heuristic argument using the undecidability of the Halting problem is the "Full Employment Theorem for Compiler Writers", which says that a fully optimizing compiler is impossible, and thus that there is always room for improvement.

Assume such a fully optimizing compiler exists. Now look at the class of programs with no inputs. If any such program does not halt, the fully optimizing compiler will generate the minimal (syntactic size optimal) non-halting program when compiling it. This is a recognizable program*, so we can solve the Halting problem for no-input programs with a fully optimizing compiler, by simply compiling the program and checking whether the resulting target program is this minimal one. And, this is as strong as solving the Halting problem in general, as we can easily code any input into a program to make it a no-input program.


---
*For instance, assume that the compiler's target language is Turing machines. The minimal non-halting no-input program is:

A b -> b 0 A

That is, a single state (A) machine, with one transition rule. If it reads a blank on the tape (b) then it writes a b back and stays at the same spot on the tape (0) and goes into the same state (A). And, of course, the program will read a blank, because it has no input. Don't get much smaller than that.

 

[Zephyr]

Another simple idea is that there are real numbers that can't be calculated using a program. Why? Irrationals are uncountable - computer programs are countable (since programs must have finite length).

One such real I read about recently is Chaitin's Ω Constant, which (for a given description of 'program') is the exact probability that a randomly generated program will halt. Knowing Ω to n binary digits allows you to solve the halting problem for any program up to that length. Knowing Ω to a few thousand places (the number depends on the definition of 'program') could answer questions like the Riemann hypothesis.

It is claimed that it may be possible to calculate Ω using quantum computation.

 

[DNA100]

May be there is a version of godel's incompleteness theorem for programming too.But................. who know?I am optimistic.

 

[Chatha]

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?

Astronomists already do that. If it can be modeled, it can be programmed. This is why even the human conditions can be someday programmed.