Re: Symbol Grounding Problem (attn: Vend)

Neil W Rickert <rickert+nn@xxxxxxxxxx> wrote on Wed, 09 May 2007:
Don Geddis <don@xxxxxxxxxx> writes:
But the surprising result of the Church-Turing work was that every model
of (physically realizable) mechanical computation that anyone had (or has)
every come up with, always winds up being equivalent (at best) to the very
simple Turing Machines.

I don't think that's true for analog computation. You would need to
restrict to discrete computation before asserting that.

Yes, you're right. I should have limited it as you suggest.

And then I don't see it as a "surprising result", since it is pretty much
what CTT says.

I meant that the Church-Turing Thesis (which has continued to be confirmed
since then) was a surprising result of the independent work that Church and
Turing (and others) were doing, to formalize computation.

I don't think people expected that such a simple model (the Turing Machine,
or recursive functions, or...) could achieve all the same computations as
far more complex machines invented over the subsequent decades.

The contrast between the simplicity of the TM's design, and the extreme
complexity of its possible computations, is surprising.

For example, look at the table at the end of
http://en.wikipedia.org/wiki/Automata_theory
It shows families of grammars, language types, and automatons, in strict
order of computational power. Before Church and Turing, one might have
imagined that the classes of such computation devices continued upwards for a
considerable period. In computer science, "common sense" suggests that
assembly language is less "powerful" than C, which is less powerful than
Java, which is less powerful than Lisp, etc.

But no, Church and Turing showed (or at least strongly suggested) that
some very simple things (recursively enumerable functions, and/or Turing
Machines) were already at the very top of what was possible.

I think that qualifies as a "surprise".

-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ don@xxxxxxxxxx
Getting tired of children? Ever heard of youthanasia?
.

Relevant Pages

  • Re: The Demise of Computationalism?
    ... "The Irrelevance of Turing Machines to AI" ... theoretical computer science (a branch of mathematics), ... machines that can interact causally with other physical systems ...
    (comp.ai.philosophy)
  • Re: Recursively enumerable sets
    ... From what I remember, Turing, in his 1936 paper "On computable numbers" ... The finiteness limitations postulated by Turing for his Turing Machines ... Philosophy of Mathematics held at Amherst College, Amherst, Massachusetts, ...
    (sci.math)
  • Re: Turing completeness of the functional paradigm?
    ... > |The Church-Turing thesis doesn't figure large in my own thinking, ... > natural numbers is Turing computable. ... We can enumerate ...
    (sci.logic)
  • Re: Foundation for a Formal Refutation of the Original Halting Problem?
    ... Turing's proof simply states that no Turing machine ... can analyze all possible Turing machines. ... claim you say you're trying to refute. ... You might, just possibly, be able to prove that there can be a Halt ...
    (sci.logic)
  • Re: DeXter IDE startup time
    ... > Turing machines vs Touring ... Sorry, the possibility of it being a joke did occur to me, and I didn't ... Both my ignorance of Turing (not Touring) and a reluctance to ...
    (borland.public.delphi.non-technical)