Hoopje
  • Member for 7 years, 1 month
  • Last seen this week
  • Germany
13 answers
176 votes
58k views
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
1 answers
5 votes
574 views
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
2 answers
5 votes
1k views
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
1 answers
3 votes
2k views
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
2 answers
9 votes
565 views
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
1 answers
1 votes
1k views
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
2 answers
-2 votes
6k views
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
1 answers
1 votes
85 views
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
1 answers
0 votes
816 views
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
3 answers
7 votes
3k views
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
1 answers
0 votes
44 views
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
1 answers
-1 votes
590 views
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
1 answers
-3 votes
63 views
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
3 answers
0 votes
121 views
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
1 answers
2 votes
5k views
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
1 answers
-2 votes
206 views
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