Sketch of a Disproof of Rice's Theorem
Continuation of "Pathological Self-Reference and the Halting Problem"
Paraphrase from page 237 of Dexter Kozen's 1997 Automata and
Computability His example proves that a TM that accepts the empty string
is undecidable. Basically I only translated his English prose into the
AnyString() pseudo-code provided below:
My adaptation shows that deciding the decidability of a TM that accepts
the empty string is decidable.
// if t(m) halts
// Accept <sigma>*
// if t(m) does not halt
// Accept NULL (Empty Set)
Boolean AnyString()
{
TM m; // Turing Machine hard-wired into finite-control
String x; // Input data hard-wired into finite-control
m(x);
return true;
}
// This function works correctly for all input that is decidable:
// 1) returns true where tm halts on input. (halts in accept state)
// 2) returns false where tm does not halt on input. (halts in reject state)
// 3) loops on undecidable input.
// function prototype
Boolean Halts(String tm, String input);
// function prototype
Boolean DecidabilityDecider(String tm, String input);
// function invocation
DecidabilityDecider(AnyString, "");
// pseudo-code of above function invocation
if (Decidable(Halts, m, x))
if (Halts(m,x))
return true;
else
return false;
else
return false;
Hypothesis:
1) For the set of possible input strings to the universal set of Turing
Machines there exists no way to show that decidability is undecidable.
2) Reduction of DecidabilityDecider(String tm, String input) to the
Halting Problem is not possible.
Reply With Quote