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

On Jun 8, 10:26 am, jones...@xxxxxxxxxxx wrote:
On Jun 6, 10:22 am, Patricia Shanahan <p...@xxxxxxx> wrote:





jones...@xxxxxxxxxxx wrote:
On Jun 4, 11:24 am, cplxp...@xxxxxxxxx wrote:
On Jun 4, 11:13 am, jones...@xxxxxxxxxxx wrote:

There are some functions that no Turing machine can compute but a
lookup table (a memory) can represent any function so is a LUT (or
memory-based reasoning system) more powerful than a Turing machine?
Related to this:
John Savage claims to have shown that "non-uniform families of
circuits" are more powerful than Turing machines. (Models of
Computation, Addison-Wesley, 1998, pgs 224 and 372).
Thoughts?     Arguments?    Opinions?
Turing machines are at least as powerful as a lookup table.  For one
thing, one could essentially "hardcode" the lookup table into a Turing
machine.

As for your claim about non-uniform families of circuits, I will have
to defer to those who are more experienced with such concepts than I
am.  (My inclination would be to say that that might be right, if I'm
properly interpreting that non-uniform families of circuits just means
that the circuits for inputs of different length are associated with
different functions.  The reason why these would be more powerful than
a TM is because you essentially have an infinite number of different
circuits.)

-Phil

Again, if I let the tape be infinite you have to let me have infinite
LUTs.
And TMs DO allow infinite tapes.

Nope. A TM's tape length is unbounded, but at any point in the
calculation it is finite. Any initial non-blank portion of the tape at
the start of the calculation is, of course, finite.

A TM can be visualized as the combination of a finite length tape and a
factory that can splice in more blank tape whenever the head approaches
the end, so that the end will never be reached.

The LUT equivalent, an always finite but unbounded size LUT, would need
a factory to supply values for rows as it grows. The plausible options,
such as a recursive function or a C program, have already been proved to
be no more powerful than Turing machines.

Patricia- Hide quoted text -

- Show quoted text -

If you google "turing machine infinite tape" you will find various
references which allow a Turing
Machine to begin with an infinite tape.

Also, if you refer to Savages's book all I want is to replace each of
his cicruits with a LUT,
I don't see how you can believe his system is more powerful than TMs
but LUTs aren't.

Or do you disagree with Savage's book?

Bob- Hide quoted text -

- Show quoted text -


Think about it like this. The algorithm you are describing can be
expressed finitely with a Turing machine; you can draw it as a
diagram, or express it equivalently as a string of 1's and 0's. Yes,
the tape is infinite; but that just means that there is no limit on
how long the input tape can become. The machine itself--which
describes the step-by-step algorithm--is still finite.

When you have an infinite family of circuits, you cannot express the
entire algorithm with a finite amount of information or description.
If you use an infinite number of lookup tables, then yes, you might
have something more powerful than a TM. (For example, if you have a
lookup table that hardcodes the correct answer to every instance of
the halting problem, that would be more powerful than a Turing
machine.) But again, you cannot express these things finitely.

It's still possible that I don't know what you mean by "non-uniform
families of circuits," but if my interpretation is correct then what
I've said is valid.

-Phil
.

Relevant Pages

  • Re: A case for HTML as a programming language
    ... but a Turing machine without an infinite tape is not a Turing ...
    (comp.programming)
  • Re: Turing machines, quantum computers, and alephs
    ... >> Turing defined a Turing machine as having an infinite tape. ... the abstract quantum computer with infinitely many qubits might start ...
    (comp.programming)
  • Re: Turing machines, quantum computers, and alephs
    ... >> Turing defined a Turing machine as having an infinite tape. ... the abstract quantum computer with infinitely many qubits might start ...
    (sci.math)
  • Re: The Modified Halting Problem, Take ??? .
    ... Turing tapes" will not be a set or even a proper class in NAFL, ... each tape itself is an infinite entity. ... They're usually described as potentially infinite or finitely unbounded. ... down or erasing binary digits one-at-a-time in the cells on a linear ...
    (sci.logic)
  • Re: Turing machines, quantum computers, and alephs
    ... > number of tape segments, but if it starts with a blank tape, or a tape ... > the abstract quantum computer with infinitely many qubits might start ... > it seems no less finite in your sense than the abstract Turing machine ... > with its infinite but mostly zeroed tape. ...
    (comp.programming)