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

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

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

Top 50 recent answers are included

#### Related Tags

computability-theory × 1013lo.logic × 559

set-theory × 169

computational-complexity × 109

computer-science × 94

reference-request × 90

model-theory × 64

descriptive-set-theory × 64

nt.number-theory × 46

proof-theory × 41

reverse-math × 39

ordinal-numbers × 38

theories-of-arithmetic × 38

decidability × 36

gr.group-theory × 35

co.combinatorics × 28

ct.category-theory × 23

constructive-mathematics × 21

algorithms × 19

computable-analysis × 17

forcing × 15

diophantine-equations × 15

recursively-enumerable × 15

soft-question × 14

it.information-theory × 14