Hoopje
• Member for 7 years, 3 months
• Last seen more than a week ago
• Germany

I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine ...

Term rewriting is a rewriting formalism. Starting with a term we rewrite the term according to the term rewriting rules until a normal form is found. Unification is finding a solution (substitution ...

Although Alan Turing is of course a very important computer scientist, the Turing test is only superficially related to computer science. It is more related to philosophy. As long as machines exist ...

If you are talking about reduction in general (not polynomial reduction), then you basically can put all the logic in the reduction function. Suppose $L_1$ and $L_2$ are decidable languages. To reduce ...

First of all, you cannot fix "suitable encoding" to be binary strings, or any other encoding. This is because you would loose too many models of computation, because different models of computation ...

You are on the right track. When constructing a DFA, you have to consider what information you need to store to decide in the end whether the string is accepted or not. The information you need is ...

First, there is a difference between a language and a grammar. A language is just a set of strings, while a grammar is a way to specify such languages. The attribute "ambiguous" applies to grammars. ...

No. A theory is a set of theorems. The set of all formulas is a decidable theory and it is an extension of all theories, including undecidable ones. It is also very inconsistent and thus useless in ...

First, to answer the question in your question title: the difference between equivalence and implication in CTL formulae is the same as the difference between equivalence and implication in ...

Since you are only working with DFAs, you can XOR two automata by building the cross product of the two automata and then taking as accepting states those pairs of states of which one state is an ...

The formula $\psi$ is called an interpolant and the method of finding such an interpolant is called Craig interpolation. On the Wikipedia article you can find more information about it, including a ...

From state 4 you cannot reach an accepting state. That means that state 4 does not contribute to the language of the automaton. Therefore you can simply delete it and then apply the state elimination ...

Yes, the word $bb$ in the language generated by the regular expression $a^*bbc^*$, because, as you say, $a^*$ and $c^*$ generate also the empty word. So if you are building a Turing machine that ...

You have asked basically the same question a few times already, so I suppose this is something you care deeply about. But as long as you don't give a definition of what a conditional is, exactly, you ...

In a strongly connected component of a graph, all nodes of the SCC must be reachable from all other nodes in the SCC. So, if $x$ and $y$ are nodes of the SCC, then there is a path from $x$ to $y$ and ...