Re: simple and beauty strategy



Why we have been traped in the puzzle all the time?whats that problem?
Answer..Halting problem

http://en.wikipedia.org/wiki/Halting_problem

In computability theory, the halting problem is a decision problem
which can be stated as follows: given a description of a program,
decide whether the program finishes running or will run forever. This
is equivalent to the problem of deciding, given a program and an
input, whether the program will eventually halt when run with that
input, or will run forever.

Alan Turing proved in 1936 that a general algorithm to solve the
halting problem for all possible program-input pairs cannot exist. We
say that the halting problem is undecidable over Turing machines.

Formal statement
The halting problem is a decision problem about properties of computer
programs on a fixed Turing-complete model of computation. The problem
is to determine, given a program and an input to the program, whether
the program will eventually halt when run with that input. In this
abstract framework, there are no resource limitations of memory or
time on the program's execution; it can take arbitrarily long, and use
arbitrarily much storage space, before halting. The question is simply
whether the given program will ever halt on a particular input.

For example, in pseudocode, the program

while True: continue
does not halt; rather, it goes on forever in an infinite loop. On the
other hand, the program

print "Hello World!"
halts very quickly.

The halting problem is famous because it was one of the first problems
proven algorithmically undecidable. This means there is no algorithm
which can be applied to any arbitrary program and input to decide
whether the program stops when run with that input.

[edit] Representing the halting problem as a set
The conventional representation of decision problems is the set of
objects possessing the property in question. The halting set

K := { (i, x) | program i will eventually halt if run with input x}
represents the halting problem.

This set is recursively enumerable, which means there is a computable
function that lists all of the pairs (i,x) it contains. However, the
complement of this set is not recursively enumerable.

There are many equivalent formulations of the halting problem; any set
whose Turing degree equals that of the halting problem is such a
formulation. Examples of such sets include:

{ i | program i eventually halts when run with input 0 }
{ i | there is an input x such that program i eventually halts when
run with input x }.

Importance and consequences
The historical importance of the halting problem lies in the fact that
it was one of the first problems to be proved undecidable. (Turing's
proof went to press in May 1936, whereas Church's proof of the
undecidability of a problem in the lambda calculus had already been
published in April 1936.) Subsequently, many other such problems have
been described; the typical method of proving a problem to be
undecidable is with the technique of reduction. To do this, the
computer scientist shows that if a solution to the new problem were
found, it could be used to decide an undecidable problem (by
transforming instances of the undecidable problem into instances of
the new problem). Since we already know that no method can decide the
old problem, no method can decide the new problem either.

One such consequence of the halting problem's undecidability is that
there cannot be a general algorithm that decides whether a given
statement about natural numbers is true or not. The reason for this is
that the proposition stating that a certain algorithm will halt given
a certain input can be converted into an equivalent statement about
natural numbers. If we had an algorithm that could solve every
statement about natural numbers, it could certainly solve this one;
but that would determine whether the original program halts, which is
impossible, since the halting problem is undecidable.

Yet another consequence of the undecidability of the halting problem
is Rice's theorem which states that the truth of any non-trivial
statement about the function that is defined by an algorithm is
undecidable. So, for example, the decision problem "will this
algorithm halt for the input 0" is already undecidable. Note that this
theorem holds for the function defined by the algorithm and not the
algorithm itself. It is, for example, quite possible to decide if an
algorithm will halt within 100 steps, but this is not a statement
about the function that is defined by the algorithm.

Gregory Chaitin has defined a halting probability, represented by the
symbol Ω, a type of real number that informally is said to represent
the probability that a randomly produced program halts. These numbers
have the same Turing degree as the halting problem. It is a normal and
transcendental number which can be defined but cannot be completely
computed. This means one can prove that there is no algorithm which
produces the digits of Ω, although its first few digits can be
calculated in simple cases.

While Turing's proof shows that there can be no general method or
algorithm to determine whether algorithms halt, individual instances
of that problem may very well be susceptible to attack. Given a
specific algorithm, one can often show that it must halt for any
input, and in fact computer scientists often do just that as part of a
correctness proof. But each proof has to be developed specifically for
the algorithm at hand; there is no mechanical, general way to
determine whether algorithms on a Turing machine halt. However, there
are some heuristics that can be used in an automated fashion to
attempt to construct a proof, which succeed frequently on typical
programs. This field of research is known as automated termination
analysis.

Since the negative answer to the halting problem shows that there are
problems that cannot be solved by a Turing machine, the Church-Turing
thesis limits what can be accomplished by any machine that implements
effective methods. However, not all theoretically possible machines
are subject to Church-Turing's thesis (e.g. oracle machines are not).
It is an open empirical question whether there are actual
deterministic physical processes that, in the long run, elude
simulation by a Turing machine. It's also an open question whether any
such process could usefully be harnessed in the form of a calculating
machine (a hypercomputer) that could solve the halting problem for a
Turing machine amongst other things. It is also an open empirical
question whether any such physical processes are involved in the
working of the human brain, thus whether humans can solve the halting
problem.[

Common pitfalls
The difficulty in the halting problem lies in the requirement that the
decision procedure must work for all programs and inputs. Every
particular program either halts on a given input or does not halt.
Consider one algorithm that always answers "halts" and another that
always answers "doesn't halt." For any specific program and input, one
of these two algorithms answers correctly, even though nobody may know
which one.

There are programs (interpreters) that simulate the execution of
whatever source code they are given. Such programs can demonstrate
that a program does halt if this is the case: the interpreter itself
will eventually halt its simulation, which shows that the original
program halted. However, an interpreter will not halt if its input
program does not halt, so this approach cannot solve the halting
problem as stated. It does not successfully answer "doesn't halt" for
programs that do not halt.

The halting problem is, in theory if not in practice, decidable for
linear bounded automata (LBAs), or deterministic machines with finite
memory. A machine with finite memory has a finite number of states,
and thus any deterministic program on it must eventually either halt
or repeat a previous state:

"...any finite-state machine, if left completely to itself, will fall
eventually into a perfectly periodic repetitive pattern. The duration
of this repeating pattern cannot exceed the number of internal states
of the machine..."(italics in original, Minsky 1967, p. 24)
Minsky warns us, however, that machines such as computers with e.g. a
million small parts, each with two states, will have on the order of
21,000,000 possible states:

"This is a 1 followed by about three hundred thousand zeroes ... Even
if such a machine were to operate at the frequencies of cosmic rays,
the aeons of galactic evolution would be as nothing compared to the
time of a journey through such a cycle" (Minsky p. 25)
Minsky exhorts the reader to be suspicious—although a machine may be
finite, and finite automata "have a number of theoretical
limitations":

"...the magnitudes involved should lead one to suspect that theorems
and arguments based chiefly on the mere finiteness [of] the state
diagram may not carry a great deal of significance" (ibid).
For more on this issue of "intractability" see Busy beaver.

It can also be decided automatically whether a nondeterministic
machine with finite memory halts on no, some, or all possible
sequences of nondeterministic decisions, by enumerating states after
each possible decision.

Formalization of the halting problem
In his original proof Turing formalized the concept of algorithm by
introducing Turing machines. However, the result is in no way specific
to them; it applies equally to any other model of computation that is
equivalent in its computational power to Turing machines, such as
Markov algorithms, Lambda calculus, Post systems, register machines,
or tag systems.

What is important is that the formalization allows a straightforward
mapping of algorithms to some data type that the algorithm can operate
upon. For example, if the formalism lets algorithms define functions
over strings (such as Turing machines) then there should be a mapping
of these algorithms to strings, and if the formalism lets algorithms
define functions over natural numbers (such as computable functions)
then there should be a mapping of algorithms to natural numbers. The
mapping to strings is usually the most straightforward, but strings
over an alphabet with n characters can also be mapped to numbers by
interpreting them as numbers in an n-ary numeral system.


Relationship with Gödel's incompleteness theorem
The concepts raised by Gödel's incompleteness theorems are very
similar to those raised by the halting problem, and the proofs are
quite similar. In fact, a weaker form of the First Incompleteness
Theorem is an easy consequence of the undecidability of the halting
problem. This weaker form differs from the standard statement of the
incompleteness theorem by asserting that a complete, consistent and
sound axiomatization of all statements about natural numbers is
unachievable. The "sound" part is the weakening: it means that we
require the axiomatic system in question to prove only true statements
about natural numbers (it's very important to observe that the
statement of the standard form of Gödel's First Incompleteness Theorem
is completely unconcerned with the question of truth, but only
concerns the issue of whether it can be proven).

The weaker form of the theorem can be proven from the undecidability
of the halting problem as follows. Assume that we have a consistent
and complete axiomatization of all true first-order logic statements
about natural numbers. Then we can build an algorithm that enumerates
all these statements. This means that there is an algorithm N(n) that,
given a natural number n, computes a true first-order logic statement
about natural numbers such that, for all the true statements, there is
at least one n such that N(n) yields that statement. Now suppose we
want to decide if the algorithm with representation a halts on input
i. We know that this statement can be expressed with a first-order
logic statement, say H(a, i). Since the axiomatization is complete it
follows that either there is an n such that N(n) = H(a, i) or there is
an n' such that N(n') = ¬ H(a, i). So if we iterate over all n until
we either find H(a, i) or its negation, we will always halt. This
means that this gives us an algorithm to decide the halting problem.
Since we know that there cannot be such an algorithm, it follows that
the assumption that there is a consistent and complete axiomatization
of all true first-order logic statements about natural numbers must be
false.




.



Relevant Pages

  • Re: Alan Turings Halting Problem is Incorrect (PART-THREE)
    ... >>or not should not accept as input TMs that neither halt nor not halt? ... but you maintain that the concept of undecidability is itself ... halting problem is reducible to it (you can solve the halting problem ... problem (that's my way of formalizing "is this program correct?" ...
    (sci.logic)
  • Re: proof of undecidability of halting problem
    ... the usual proof of the undecidability of the halting problem does so by ... however, the contradiction is introduced by using a second function, ... a function like halt can't? ...
    (sci.logic)
  • Re: The halting problem
    ... meanning to halt when H outputs "HALT" and loop when H " outputs ... if the halting problem were decidable, and its existence causes H to ... complete the proof is that there exists an algorithm that messes up H, ... know the mechanics of how Turing machines work to understand the ...
    (comp.theory)
  • Re: The halting problem
    ... meanning to halt when H outputs "HALT" and loop when H " outputs ... if the halting problem were decidable, and its existence causes H to ... complete the proof is that there exists an algorithm that messes up H, ... know the mechanics of how Turing machines work to understand the ...
    (comp.theory)
  • Re: The halting problem
    ... meanning to halt when H outputs "HALT" and loop when H " outputs ... if the halting problem were decidable, and its existence causes H to ... complete the proof is that there exists an algorithm that messes up H, ... know the mechanics of how Turing machines work to understand the ...
    (comp.theory)