The undecidability tag has no wiki summary.
-1
votes
0answers
23 views
Undecidability of whether a given TM has only mechanically detectable loops or always halts
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 ...
1
vote
0answers
40 views
loop invariants in proving program termination
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 ...
-6
votes
0answers
69 views
Show that it is undecidable if two TMs accept the same language [closed]
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!
3
votes
1answer
95 views
Decidability in Extensional Type Theory
What are the ways in which one can add a decidable equivalence relation in a type system with undecidable type checking/extensional equality?
5
votes
0answers
166 views
Eliminate ambiguity from CFG
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 ...
10
votes
3answers
2k views
Does P contain languages whose existence is independent of PA or ZFC? (TCS community wiki)
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 ...
