New answers tagged computability-theory
1
vote
Accepted
What is the computational complexity to verify a P solution with a deterministic Turing machine?
In general it is computationally undecidable to determine if a given program $p$ solves a given decision problem, and also to decide whether it does so in polynomial time. For example, consider the ...
- 232k
6
votes
Accepted
Are (group theoretic) Markov properties on groups with decidable word problems, decidable?
There are several distinct algorithmic problems that you are referring to.
First of all, we can consider decision problems for finitely presented groups with solvable word problem given by finite ...
- 533
3
votes
Undecidability of the existential theory
This is Theorem 1, p. 530 in paper [1] by Pheidas.
Reference
[1] Thanases Pheidas, "An undecidability result for power series rings of positive characteristics. II." Proceedings of the ...
- 31
Top 50 recent answers are included