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

From: Martin Shobe (mshobe_at_sbcglobal.net)
Date: 08/24/04 

Date: Tue, 24 Aug 2004 23:34:42 GMT

On Tue, 24 Aug 2004 16:54:02 +0000 (UTC), dj3vande@csclub.uwaterloo.ca
(Dave Vandervies) wrote:

>In article <95hei0dk8oe8gq4g6h1a8rpjnvrj8m921q@4ax.com>,
>Martin Shobe <mshobe@sbcglobal.net> wrote:
>>On Fri, 20 Aug 2004 20:38:32 +0000 (UTC), dj3vande@csclub.uwaterloo.ca
>>(Dave Vandervies) wrote:
>>
>>>In article <d21rh0lc2ed6m1d768422ftvcalo6vkh1j@4ax.com>,
>>>Martin Shobe <mshobe@sbcglobal.net> wrote:
>>>
>>>>I'm going to regret this but.... There are things that can solve the
>>>>halting problem for TM's. They just have to be *more* powerful than a
>>>>TM.
>>>
>>>Show us one.
>>
>>It was in the part of the message you clipped.
>
>You mean this one?
>}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.

Martin

Relevant Pages