Hoopje
  • Member for 7 years, 3 months
  • Last seen more than a week ago
  • Germany
Why, really, is the Halting Problem so important?
25 votes

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

View answer
Term Rewriting vs Unification
Accepted answer
13 votes

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

View answer
How is a Turing Test defined?
Accepted answer
10 votes

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

View answer
Could two decidable languages ever not have a mapping reduction?
Accepted answer
6 votes

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

View answer
Is there a clear definition of "computable" for models of computation which are not turing complete?
4 votes

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

View answer
How to write a DFA where the second digit is equal to the last digit of binary strings?
Accepted answer
4 votes

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

View answer
Ambiguous Grammar to Unambiguous Grammar
Accepted answer
4 votes

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

View answer
Is the extension of every undecidable theory undecidable?
3 votes

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

View answer
Difference between equivalence and implication
Accepted answer
3 votes

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

View answer
How to XOR automata?
2 votes

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

View answer
Prove the existence of a proposition logical formula so that following conditions are fulfilled
Accepted answer
2 votes

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

View answer
Converting DFA to regular expression
Accepted answer
2 votes

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

View answer
The meaning of $*$ in regular expressions
Accepted answer
2 votes

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

View answer
Where does the need for conditionals (if, switch, jump tables, etc...) truly arise?
1 votes

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

View answer
Resolving ambiguity in dangling else
1 votes

I assume that one can also derive some atomic statements from <STMT> and <E-STMT>, otherwise the language of both grammars would be empty and all would be quite trivial. :-) But that aside:...

View answer
Strongly connected components in graph
Accepted answer
1 votes

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

View answer