On Thu, Apr 17, 2008 at 3:09 PM, Eivind Eklund <eeklund / gmail.com> wrote:
> On Thu, Apr 17, 2008 at 12:26 PM, Phillip Gawlowski
>  <cmdjackryan / googlemail.com> wrote:
>  > -----BEGIN PGP SIGNED MESSAGE-----
>  >  Hash: SHA1
>  >
>  >  Eivind Eklund wrote:
>  >
>  >  |
>  >  | The Goedel proof is about complete logical systems; in the case of a
>  >  | computer program, we are working with a system where we have other
>  >  | formalisms under it that's providing axioms that we don't prove, just
>  >  | assume.
>  >
>  >  But a language that is Turing-complete is a complete logical system, is
>  >  it not?
Forgive me to add a comment as Eivind has been much clearer than me on
the description of what is the Halting Problem and Completeness. I
also think it was nice to add that your posts are very valuable
usually, I agree indeed.
But your last question can maybe be explained in simple words.

Being turing-complete means in theory that you can solve all problems
that a Turing Machine can solve (given unlimited memory) (1).
E.g.
Ruby being turing-complete means therefore that you can write a Ruby
program of which one can not determine if it will halt or not. But
chances are slim that such a Ruby program is written by chance, and
furthermore it would need infinite memory.



(1) A TM that solves a problem halts and it if halts it can only use a
finite amount of its endless tape, so theoretically Ruby
can do the same thing even if there is no limit of memory that can be
established :)

<snip>

Cheers
Robert

-- 
http://ruby-smalltalk.blogspot.com/

---
Whereof one cannot speak, thereof one must be silent.
Ludwig Wittgenstein