This might be a bit of an abstruse question, but it's something I've been trying to prove. I'm trying to show that it is undecidable whether a given Turing Machine is a member of the set of all ...
consider two similar pieces of (pseudo)code: A: n = f(x) for (i = 1 to n) do begin .... end B: x = 1 while (x != 0) do begin x = g(x) .... end in case A if ...
I was asked this question at an interview, and couldn't answer it, and would like to know how it is 'shown'. This is NOT HW!
What are the ways in which one can add a decidable equivalence relation in a type system with undecidable type checking/extensional equality?
CFG here stands for context-free grammar. I understand that: Deciding whether a CFG $G$ is ambiguous is undecidable. Deciding whether a CFL $L$ is inherently ambiguous is undecidable. My question ...
Answer: not known. The questions asked are natural, open, and apparently difficult; the question now is a community wiki. Overview The question seeks to divide languages belonging to the ...