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.
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.
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 matroid being representable is equivalent to a certain locally closed subscheme of the Grassmannian, defined by the non-vanishing of the Plücker coordinates corresponding to bases and the vanishing of the Plücker coordinates coordinates corresponding to non-bases, being nonempty. This can be done (using Gröbner basis algorithms) in a few different ways.
In the paper Singular matroid realization spaces, Dan Corey and Dante Luber have written code in OSCAR which does this, apparently quite efficiently. Remarkably, they were able to determine exactly which matroids of rank 3 on 11 elements are realizable over $\mathbb{C}$.
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.
