Re: What is the Result from Invoking this Halt Function?

From: Dave Vandervies (dj3vande_at_csclub.uwaterloo.ca)
Date: 08/25/04 

Date: Wed, 25 Aug 2004 00:52:56 +0000 (UTC)

In article <mvjni09q7vj0anglmtai2ol583h9l746r3@4ax.com>,
Martin Shobe <mshobe@sbcglobal.net> wrote:
>On Tue, 24 Aug 2004 16:54:02 +0000 (UTC), dj3vande@csclub.uwaterloo.ca
>(Dave Vandervies) wrote:

[reintroducing an earlier quote from Martin Shobe]
>>}For example, if you start with the definition of a TM but replace
>>}the finite set of states with a countable set of states,
>>
>>If we have a countable set of states, we can store the state table on
>>one tape in a two-tape turing machine (which is equivalent to a one-tape
>>turing machine, just sometimes more convenient to work with). The TM
>>then keeps the countable-state-machine's state as the location on tape 1,
>>and treats tape 2 as the countable-state-machine's tape.
>>
>>Can somebody who knows what they're talking about give a less handwavey
>>description of why this would be equivalent to a TM, or point out
>>why I'm wrong? The only potential problem I can see is getting the
>>countable-state-machine program on the tape in the first place - are
>>we allowed to just say it's there before the machine starts? If not,
>>is it possible to construct a TM that would be able to write the program
>>to the tape and then run the interpreter TM (or, possibly easier to
>>handle description-wise, run the interpreter TM while making sure that
>>each location on the program tape is written no later than just before
>>the interpreter tries to seek to it)?
>
>I was under the impression that there could only be a finite number of
>non-blanks at the start.

If that is the case, then it would of course be hard to start it up with
an infinitely long program on the tape.
(Can somebody who knows what they're talking about verify this one way
or the other?)

What about the idea of constructing a machine that can run the interpreter
and suspend it to write the next part of the program when it tries to
seek past the initialized part of the program tape? Does trying to
generate every possible countable-state-machine-with-tape with some
finite-state-machine-with-tape program fall to the diagonal argument?
(Having seen your explanation elsethread of the existence of a countable-
state-machine that can solve the turing-machine halting problem, I'm
pretty sure it would have to fall to something, if not this.)

dave 

-- 
Dave Vandervies                           dj3vande@csclub.uwaterloo.ca
Getting a consensus from comp.lang.c would make you a strong candidate
for a Nobel Prize.
                                   --Richard Heathfield in comp.lang.c

Relevant Pages

  • Re: What is the Result from Invoking this Halt Function?
    ... >(Dave Vandervies) wrote: ... [reintroducing an earlier quote from Martin Shobe] ... >>to the tape and then run the interpreter TM (or, ... >>each location on the program tape is written no later than just before ...
    (sci.logic)
  • Re: What is the Result from Invoking this Halt Function?
    ... >If we have a countable set of states, we can store the state table on ... >turing machine, just sometimes more convenient to work with). ... >to the tape and then run the interpreter TM (or, ... >each location on the program tape is written no later than just before ...
    (sci.logic)
  • Re: What is the Result from Invoking this Halt Function?
    ... >If we have a countable set of states, we can store the state table on ... >turing machine, just sometimes more convenient to work with). ... >to the tape and then run the interpreter TM (or, ... >each location on the program tape is written no later than just before ...
    (comp.theory)