Re: Recursive language which is not context-sensitive

On 15 May, 09:58, sanchopanch...@xxxxxx wrote:
On 15 Mai, 10:08, Derek Holt <ma...@xxxxxxxxxxxxx> wrote:



On 14 May, 09:26, sanchopanch...@xxxxxx wrote:

Hello,

i don't understand something in the proof that there is a recursive
language which is not context-sensitive: one uses a diagonal argument.
Therefore one has to consider the ordered set S of turing machines T_i
which accept context sensitive languages oder a given alphabet and
constructs a language over the alphabet which is not accepted by each
T_i of S beacuse it containes exactly the words w_i which are not
accepted by T_i. Hence the language is not context-sensitive.

More precisely the construction of S is as follows: Take a context
sensitive Grammar G and build up a turing machine T which accepts the
language which is defined by G.

Now the argument is that this recursive! But therefore you have to
build a turing machine which constructs the set S!

You can effectively enumerate the context sensitive grammars. So there
is an algorithm, which, given a natural number, like 37, can write
down the 37th context sensitive grammar. There is another algorithm,
which, given a context sensitive grammar, can output a Turing
machine, T_37 say, which accepts the language defined by this
grammar. Of course, each context sensitive language will be defined by
many different grammars, but that does not matter.

Words can also be effectively enumerated, so given a word w, there is
an algorithm that finds its number, say 37, and then constructs T_37,
and checks whether or not T_37 accepts w. (We can assume that the
Turing machines are deterministic.) Our diagonal Turing machine D that
we are constructing will accept w if and only T_37 does not accept w.
Now D is a Turing machine of which the language L(D) cannot be equal
to any of the L(T_i), so L(D) cannot be context sensitive.

How is this
possible? More precisely you have to have a turing machine which
generated all context sensitive grammars. I mean you can encode a
context sensitive grammar over the alphabet but how you can decide
weather a given 'input string' encodes a context sensitive grammar or
is just a garbage string?

You cannot decide that but you do not need to be able to decide that.

(You can't decide the weather either!)

Derek Holt.

Thank you for your answer. I understand everything in the argument but
this

You can effectively enumerate the context sensitive grammars. So there
is an algorithm, which, given a natural number, like 37, can write
down the 37th context sensitive grammar

is still unclear to me. How can this be done more precisely?

A context sensitive grammar can be defined as a list (N, Sigma, S,
P_1, P_2, ..., P_r), where N and Sigma are the numbers of non-
terminals and terminals, S is the start symbol (so 1<=S<=N) and P_i
are the productions. Each production is a pair of words (u_i,v_i) with
1<=|u_i|<=|v_i| over the terminals and non-terminals, so we can think
of u_i and v_i as being strings of integers u_i1,...,u_is with each
integer in the string between 1 and N+S. So, you could, for example,
represent the whole grammar by a string of non-negative integers of
the form
(N, Sigma, S, 0, u_11, u_12, ..., u_1s, 0, v_11, ..., 0, u_21, ... )

Now order all finite sequences of non-negative integers in some
suitable fashion. For example, we could order them first by sum of
entries + length, then lexicographically. i.e.

() < (0) < (0,0) < (1) < (0,0,0) < (0,1) < (1,0) < (2) < (0,0,0,0) <
(0,0,1) < (0,1,0) ...

Of course, most of these sequences do not represent context sensitive
grammars as described above, but for each of them we can easily check
whether it does. So we just write those down in order that do
represent context sensitive grammars, and stop at when we have 37 of
them.

Derek Holt.
.

Relevant Pages

  • No Set Contains Every Computable Natural (was Church-Turing compared to Zuse-Fredkin thesis)
    ... A decidable or recursive language is a formal language that is a recursive ... YES/NO answer for any input string after a finite amount of time. ... A non-deterministic Turing machine is an example of a hypercomputer. ... There is only a finite number of naturals ...
    (comp.theory)
  • Re: Entropy
    ... You'll find there exactly the same elementary result I stated above, namely that the complexity is language dependent, and that for any two languages the complexity of a given string differs by a constant. ... For any message A there exists a Turing machine U such that C_U= 1. ...
    (comp.compression)
  • Re: Recursive language which is not context-sensitive
    ... language which is not context-sensitive: ... More precisely the construction of S is as follows: Take a context ... sensitive Grammar G and build up a turing machine T which accepts the ... down the 37th context sensitive grammar. ...
    (sci.math)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... Language Q1 is the ... then you cannot say that Q is union of Q1 and Q2 without some merge done. ... "ABABABABAe" doesn't look like a Turing machine at all, ... Union means that every string from each set is also in union and we expect that ANSWER asociated with string is the same. ...
    (comp.theory)
  • OT: Church-Turing thesis (was Re: TCL cant do as much as Perl)
    ... Well, there's always the technical, trivial proof from Computer Science: either language can be used to simulate a Turing Machine, thus they are equally powerful, and no language can exist that is more powerful. ... the thesis states that a universal Turing machine (UTM) is able to compute any function which can be computed by an "effective method". ... An effective method is defined as being those tasks which an unaided human could in principle achieve, using just pencil and paper, following a finite number of instructions, in a finite number of steps, without using intuition etc. ...
    (comp.lang.tcl)