Re: Is memory-based reasoning more powerful than Turing machine?

On Jun 11, 12:39 pm, tc...@xxxxxxxxxxxxx wrote:
In article <4a313a8a$0$491$b45e6...@xxxxxxxxxxxxxxxxxxxxxxxxx>, I wrote:
If the world contains an infinite number of (independent) bits of
information, then Turing machines, LUTs, and circuits are all equally
powerful in the sense that they can compute any (discrete) function.

I should perhaps have been more precise about what I meant by a "(discrete)
function."  I meant any function from the integers to the integers.  The
point is that the world could, in principle, contain all the values of the
function, and all you have to do is go to the right part of the world to find
the answer.

However, if the world contains infinitely many bits, then in particular it
can store *all* the bits of an arbitrary real number.  You might therefore
raise the bar and ask if a Turing machine or LUT or whatever can compute any
function from the *reals* to (say) the set {0,1}.

The answer is no.  This is easily seen by a counting argument: There are far
too many such functions to be encoded by a digital computer.

Nevertheless, there are some interesting things that can be said about this
kind of setup.  See for example the book 'Computable Analysis' by Weihrauch.
--
Tim Chow       tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth.  ---Galileo, Dialogues Concerning Two New Sciences

A memory-based reasoner records patterns from the world. Otherwise it
wouldn't even
have "memory." But it's not clear to me how a Turing machine can do
this. In
fact the claim is there are some functions a TM can not compute (but
the
memory based reasoner will be able to do so).

Notice that if a memory-based reasoner is more powerful than a Turing
machine
then humans would probably also be more powerful than TMs. These are
some
of the issues I am interested in.

Bob
.

Relevant Pages

  • Re: Question on Chaitin
    ... >> I've tried to correct some of your ignorant claims about philosophy ... modeled as, a digital computer or Turing machine, is too vague to apply ... undermined by the incompleteness theorems. ... There is no question of what set a given Turing machine ...
    (sci.logic)
  • Re: Is memory-based reasoning more powerful than Turing machine?
    ... memory-based reasoning system) more powerful than a Turing machine? ... circuits has an infinite amount of information hardcoded into it. ... CONTENTS would be patterns seen in the world and read into the LUTs. ...
    (comp.theory)
  • Re: Poll: Are PCs Turing Machines?
    ... > PC as a hybrid system with an uncountably large state space, ... "A Turing machine is a kind of state machine. ... I think because there are real numbers that a digital computer does not ... Maybe this isn't the best reason, a continuous vs. discrete ...
    (sci.math)
  • Re: Poll: Are PCs Turing Machines?
    ... > PC as a hybrid system with an uncountably large state space, ... "A Turing machine is a kind of state machine. ... I think because there are real numbers that a digital computer does not ... Maybe this isn't the best reason, a continuous vs. discrete ...
    (comp.theory)