Late Night Meeting of Gödel and Turing?
Hacking together concepts from mathematical analysis, mathematical logic, and computer science and finding similarities while half asleep can be fun! :-)
This night there’s been an interesting lecture and discussion at the brmlab hackerspace in Prague. During the explanation of the Halting Problem I was struck by its similarity to Gödel's results in logic.
Gödel proved that any strong (ω-consistent or ω-complete) theory must be necessarily incomplete or contradictory. The Halting Problem shows that any Turing-complete system cannot have a HALT function analyzing the finality of algorithms without running them. And both facts are proved using the same vicious concept: self-reference!
I couldn't help but wonder whether HALT could exist at least on a class of non-self-referencing programs. But then: how do we define such a class? And is it still useful?
To define a filter identifying self-referencing programs, I shackled together a concept based on recognizing something like non-converging idempotence of function iteration with respect to the input parameter(s). The idea being that self-referencing functions can be iteratively composed with themselves and this sequence cannot converge in input parameters (i.e. an endless recursion is created). The non-convergence would be proved with something like a Bolzano-Cauchy condition. I don’t know if this idea works, or if it’s possible to define self-referencing programs at all. But it sure was fun thinking of recursive functions in terms of metric spaces :-)
But then, would a class of non-self-referencing functions still be interesting? I don’t think so. We agreed with Pasky that it would probably not be Turing-complete any more. I.e. useless. Here the analogy with Gödel really makes sense – a theory strong enough breeds self-references and hence imperfection. And Turing-completeness breeds self-referencing programs and hence the undecidability of the Halting Problem.
One of the reasons I admire Spinoza is his drive towards unity and reconciliation of theories. It’s my nature, too.
1 comment Add your own…
Speak your mind
Allowed HTML tags are a, blockquote, em, code, li, ol, p, pre, strong, ul. Links to other comments in the form “[IV]” or “[4]” are detected automatically.