New answers tagged computability
0
Suppose we can find $G’$ - a grammar with the fewest variables and equivalent to $G$ - with the help of a Turing machine $T$.
Thus there exists $T$ taking input $G$ and giving output $G’$. Suppose that $G’$ is unique up to relabeling of variables.
Then we can use this $T$ to decide ${EQ_{CFG}}^1$ ; i.e. by applying $T$ on $G_1$ and on $G_2$ and deciding if ...
0
Let $L \neq \emptyset$ be a language over some alphabet $\Sigma$, let $|$ be a symbol not in $\Sigma$, and consider the language $|L = \{ |w : w \in L \}$. Suppose that $L$ could be generated using a context-free grammar with a single nonterminal $S$.
Since $L \neq \emptyset$, $S \Rightarrow^* |w$ for some word $w$. Therefore:
Every rule contains at most ...
-3
If a programming language has "branch (e.g. if)" and "loop (e.g. for/while)", it is Turing-complete, and vice versa. Having "branch" and "loop" is necessary and sufficient conditions for Turing-completeness. Haskell's recursion is a kind of loop.
0
The length of the smallest C program that generates a given string is known as the Kolmogorov complexity of the string. One of the basic properties of Kolmogorov complexity is its undecidability.
2
Your question is very philosophical in nature because you are asking about what is considered by computation and it’s physical implementations. In short, there is a ongoing discussion on different accounts of concrete computation e.g. the simple mapping account, the semantic account, the syntactic account, the mechanistic account, the causal, the ...
2
$D$ verifies $\langle M \rangle$ is a (deterministic) TM and then builds the configurations graph and checks if the initial configuration of $\epsilon$ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't.
The problem here is that, even if you define the TM so that there are only finitely many ...
2
I think you are really asking a question about the definition of the notion of well-foundedness.
I think the notion of loop variants is a bit of a red herring here: I would argue that any reasonable definition of well-foundedness should enable proving that a loop is terminating iff there is a well-founded relation which acts as a variant for it, almost as a ...
0
then builds the configurations graph and checks if the initial configuration of ϵ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't.
The above is just another way of saying: run $M$ on $\epsilon$ and wait to see if the machine halts or not. This, hovewer, is not deciding the language $L$.
0
A language is a decision problem. $L \subseteq \{0,1\}^*$, a generic language, is a subset of $\Sigma^*$ (where $\Sigma$ is the alphabet).
Decidable languages are by definition countable, as every Turing Machine has a finite description.
We can prove that there is no bijective mapping between the set of all turing machines to the set of all subsets of $\...
1
Humans can solve some instances of undecidable problems and so can computers. Computers cannot solve all instances of undecidable problems, and not can humans.
1
any location except i/p part means
(total unbounded tape area - tape area that includes i/p string)
= (infinity length - finite length) as we know i/p string length is always finite
= infinity length
in the definition of linear bounded automata it is stated that the tape can be used as a function of the input string length.but here the portion that can ...
2
Yes. See the notion of an approximation-preserving reduction.
Top 50 recent answers are included
