58k views

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 ...

574 views

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 ...

1k views

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 ...

2k views

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 ...

565 views

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 ...

1k views

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 ...

6k views

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. ...

85 views

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 ...

816 views

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 ...

3k views

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 ...

44 views

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 ...

590 views

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 ...

63 views

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 ...

121 views

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 ...

5k views
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 ...