Prev: a^4+b^3=c^2
Next: Where did term Non-Functional come from?
From: Sadeq on 7 Aug 2007 04:01
I'm reading the book "computational complexity; a modern approach."
The book defines some languages in a way I don't understand. For
example, the following language is calimed to be in PSPACE-complete:

SPACETM = { <M, w, 1^n> : DTM M accepts w in space n} .

Can anyone explian this? The problem is, I don't undesrtand what "w"
and "1^n" are, and how they are related.

From: Proginoskes on 7 Aug 2007 04:20
On Aug 7, 1:01 am, Sadeq <MSDou...(a)gmail.com> wrote:
> I'm reading the book "computational complexity; a modern approach."
> The book defines some languages in a way I don't understand. For
> example, the following language is calimed to be in PSPACE-complete:
>
> SPACETM = { <M, w, 1^n> : DTM M accepts w in space n} .
>
> Can anyone [explain] this? The problem is, I don't undesrtand what "w"
> and "1^n" are, and how they are related.

"w" is some input string. "1^n" is most likely the string containing n
1's (unary numeral for n).

As for "space n": Turing machines run using a tape with an infinite
number of squares. However, if a TM accepts the input, it has to stop.
It can only stop after a finite number of steps, and so it only uses
finitely many of those squares (since you only look at <= 1 new square
per step).

If the Turing machine M is given the string 101 and M accepts this
string, it has used a certain number of squares on the tape; say 5.
Then this means that
<M, 101, 11111> is in the set SPACETM. (Presumably there is a coding
system used that produces strings for M, for 101, and for 11111, and
<M,101,11111> is really converted into a single string, which is
really the language SPACETM.)

--- Christopher Heckman

From: Sadeq on 7 Aug 2007 07:31
On Aug 7, 11:20 am, Proginoskes <CCHeck...(a)gmail.com> wrote:
> On Aug 7, 1:01 am, Sadeq <MSDou...(a)gmail.com> wrote:
>
> > I'm reading the book "computational complexity; a modern approach."
> > The book defines some languages in a way I don't understand. For
> > example, the following language is calimed to be in PSPACE-complete:
>
> > SPACETM = { <M, w, 1^n> : DTM M accepts w in space n} .
>
> > Can anyone [explain] this? The problem is, I don't undesrtand what "w"
> > and "1^n" are, and how they are related.
>
> "w" is some input string. "1^n" is most likely the string containing n
> 1's (unary numeral for n).
>
> As for "space n": Turing machines run using a tape with an infinite
> number of squares. However, if a TM accepts the input, it has to stop.
> It can only stop after a finite number of steps, and so it only uses
> finitely many of those squares (since you only look at <= 1 new square
> per step).
>
> If the Turing machine M is given the string 101 and M accepts this
> string, it has used a certain number of squares on the tape; say 5.
> Then this means that
> <M, 101, 11111> is in the set SPACETM. (Presumably there is a coding
> system used that produces strings for M, for 101, and for 11111, and
> <M,101,11111> is really converted into a single string, which is
> really the language SPACETM.)
>
> --- Christopher Heckman

Thanks very much! Now I got it.

From: Proginoskes on 7 Aug 2007 22:50
On Aug 7, 4:31 am, Sadeq <MSDou...(a)gmail.com> wrote:
> On Aug 7, 11:20 am, Proginoskes <CCHeck...(a)gmail.com> wrote:
>
> > On Aug 7, 1:01 am, Sadeq <MSDou...(a)gmail.com> wrote:
>
> > > I'm reading the book "computational complexity; a modern approach."
> > > The book defines some languages in a way I don't understand. For
> > > example, the following language is calimed to be in PSPACE-complete:
>
> > > SPACETM = { <M, w, 1^n> : DTM M accepts w in space n} .
>
> > > Can anyone [explain] this? The problem is, I don't undesrtand what "w"
> > > and "1^n" are, and how they are related.
>
> > "w" is some input string. "1^n" is most likely the string containing n
> > 1's (unary numeral for n).
>
> > As for "space n": Turing machines run using a tape with an infinite
> > number of squares. However, if a TM accepts the input, it has to stop.
> > It can only stop after a finite number of steps, and so it only uses
> > finitely many of those squares (since you only look at <= 1 new square
> > per step).
>
> > If the Turing machine M is given the string 101 and M accepts this
> > string, it has used a certain number of squares on the tape; say 5.
> > Then this means that
> > <M, 101, 11111> is in the set SPACETM. (Presumably there is a coding
> > system used that produces strings for M, for 101, and for 11111, and
> > <M,101,11111> is really converted into a single string, which is
> > really the language SPACETM.)
>
> Thanks very much! Now I got it.

Good! I didn't know how much detail to go into there.

--- Christopher Heckman

 | 
Pages: 1
Prev: a^4+b^3=c^2
Next: Where did term Non-Functional come from?