Is matroid realizability computable? I attended a talk which generalized matroid realizability over a field to matroid realizability over division rings, and showed that the question of realizability is undecidable. However, they used a word problem arising from the division ring.
Is it known whether the question of "Is a matroid M realizable over any field F" is computable?
It seems to me that it shouldn't be, because they you would have a prover of all theorems akin to the Pappus theorem, but that's just my intuition.
 A: Sam Hopkins has answered what I think is your stated question.  But in the comments, it seems that you're also interested in the following question: Given a matroid $M$ and field $F$, is it decidable whether $M$ is $F$-representable?
In Oxley's book Matroid Theory (2nd edition), he discusses this problem on pages 226–227. If $F$ is a finite field then decidability is trivial since the rank of the matroid tells you the dimension of the vector space to try.  For infinite fields the situation is more subtle; for starters, one has to address the question of what it means to be "given" $F$.  Gröbner basis algorithms may solve the problem if $F$ is algebraically closed.  On the other hand, Sturmfels (On the decidability of Diophantine problems in combinatorial geometry, Bull. Amer. Math. Soc. 17 (1987), 121–124) has shown that for $F=\mathbb{Q}$, the question is equivalent to Hilbert's 10th problem for $\mathbb{Q}$, which remains an open problem at the time of this writing.
A: Contra my suspicions, the Internet is telling me that Vámos proved in "A necessary and sufficient condition for a matroid to be linear" (citation below) that it is decidable if a matroid is representable over a field. See quote on pg. 3 of Solving Rota’s Conjecture which says "The first exception is the algorithmic problem of determining when a given matroid is representable over an unspecified field, which was proved to be decidable by Vámos [28]."
Vamos, P., A necessary and sufficient condition for a matroid to be linear, Möbius Algebras, Conf. Proc. Waterloo 1971, 162-169 (1975). ZBL0374.05017.
EDIT:
Since the Vámos reference seems hard to track down, let me quote from the MathReviews [MR0349447] by J. E. Graver, which gives more details about the result:

The author gives a necessary and sufficient condition for a matroid to be $f$-linear, i.e., representable over some field. Let $E$ be a set and $\scr{E}$ a collection of subsets of $E$ satisfying the conditions for the independent sets of a matroid on $E$. We denote this matroid by the pair $(E,\mathscr{E})$. Fix $B\in \mathscr{E}$, a basis for the matroid. For each $x\in E$ define $S(a)$ as follows: $S(a)=\varnothing$ if $\{a\}\notin \mathscr{E}$; $S(a)=\{a\}$ if $a\in B$; otherwise $S(a)$ is the unique subset of $B$ such that $S(a)∪\{a\}$ is a circuit. Let $\Gamma=\{(a,b):a\in E,b\in S(a)\}$, and consider $R=Z[X_{\gamma}]$, the ring of polynomials over the integers in variables $\{X_\gamma: \gamma \in \Gamma\}$. A finite subset $A \subseteq E$ is said to be regular if $|A|=|\bigcup_{a \in A}S(a)|$. For each regular set $A$ a polynomial in $R$ is constructed as follows: Let $r_{(a,b)}=X_{(a,b)}$ if $a \in A$ and $b \in S(a)$, and $r_{(a,b)}=0$ if $a\in A$ and $b\in A−S(a)$. Ordering the elements of $A$, constructing the $|A|\times |A|$ matrix $[r_{(a,b)}]$ and taking the determinant yield a polynomial $P(A)$, unique up to sign. However, the ideal $I$ generated by $\{P(A):\textrm{$A$ is regular}, A\notin \mathscr{E}\}$ and the multiplicatively closed set $T$ generated by $\{P(A):\textrm{$A$ is regular}, A\in \mathscr{E}\}$ are uniquely determined. We may now state the main result. Theorem: The matroid $E, \mathscr{E}$ is $f$-linear if and only if $T\cap I=\varnothing$.

Note that in the review there is a confusing typo where it describes $T$ as generated by $\{P(A):\textrm{$A$ is regular}, A\notin \mathscr{E}\}$ rather than $\{P(A):\textrm{$A$ is regular}, A\in \mathscr{E}\}$. Note also, as pointed out in the comments by Geva Yashfe, that this result appears as Theorem 6.8.9 in the 2nd edition of Oxley's Matroid Theory text, which is probably a more accessible source. To deduce decidability from this algebraic crieterion, Oxley appeals to Gröbner basis theory.
A: Being decidable is a very weak property - one can also ask about the exact complexity class of this problem.  In fact, post-Mnёv theorem this is extremely well understood.  I recommend Matoušek's survey which explains why over $\Bbb R$ the problem is $\exists\Bbb R$-complete.  Here "realizability" in the special case of rank $3$ oriented matroids becomes a question of "stretchability" of pseudoline arrangements.
