Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

New answers tagged

0

Consider a standard coding of Turing machine $T_0$, $T_1$, $T_2$, ... Let $b : \mathbb{N} \to \mathbb{N}$ be a non-computable bijection. Define a new coding of Turing machines $T'_n = T_{b(n)}$. Clearly, the encoding $T'$ can do everything that Turing machines can do (whatever you do with $T$ you can do with $T'$ by composing with $b$ and its inverse), but ...


-1

Any context-sensitive language is decidable and can be recognised by a Turing machine in NLINSPACE. Recognising a string from an arbitrary deterministic context-sensitive grammar is PSPACE-complete. Moreover, just as context-free languages are equivalent to NPDAs, context-sensitive languages are equivalent to linear-bounded automata. Every CSL can be ...


2

Context-sensitivity has nothing to do with the semantics of a language. A language could have an arbitrarily complicated grammar, and still not be able to do anything useful, perhaps because it has no looping construct. To make the above possibly clearer, here's a simple example. We know that it is possible to list all Turing machines in some order. (The ...


0

I don't think that's the case. Looks to me that you are questioning if the Turing-completeness is specification-wise or implementation-wise. And the answer is in the specification-wise. If I have a language A, I've specified its semantics - and it is not Turing complete by definition (say, CSS for example). This means that whatever compiler you write will ...


Top 50 recent answers are included