(this is a cross-post from mathoverflow)
Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight). Assume that each node has a unique identifier.
Let's say I then have an input, $c$ of three edges (e.g $c=[4,7,6]$).
Does an algorithm exist that lets me search $G$ for instances of $c$, and returns the identifiers of the matching nodes?
The cycles it returns must be closed loops, such as $[A, D, B, \text{(then back to A)}]$, rather than $[D, A, B, A]$
Here is a poorly-drawn example:
.

The claim is not that a computer cannot determine the validity of some mathematical statements. Rather, the claim is that there is a class $\mathcal{C}$ of mathematical statements such that no algorithm can decide, given a statement from class $\mathcal{C}$, whether it is valid or not.
The standard choice for the class $\mathcal{C}$ is statements about natural numbers, for example:

Every even integer greater than two is a sum of two primes.

The class $\mathcal{C}$ contains all statements of the form:

For all natural $n_1$ there exists natural $n_2$ such that for all natural $n_3$ there exists natural $n_4$ such that ... there exists natural $n_{2m}$ such that $P(n_1,\ldots,n_{2m})$,

where $P$ is an expression using logical operators, comparison operators, addition, subtraction, multiplication, division, and integer constants.
Another popular choice for the class $\mathcal{C}$ is:

The following algorithm halts: ...

In both cases, there is no algorithm that takes an arbitrary statement from class $\mathcal{C}$ and correctly outputs whether the statement is valid or not.

It is crucial that the algorithm be required to answer correctly for all statements in $\mathcal{C}$. We can easily write an algorithm that answers correctly on a single statement from $\mathcal{C}$. Indeed, one of the following algorithms will work:

The statement is valid.


The statement is not valid.

Similarly, we can design an algorithm that answers correctly on two different statements $A,B$. One of the following will work:

The statement is valid.


The statement is not valid.


If the statement is $A$, then it is valid, otherwise it is not valid.


If the statement is $B$, then it is valid, otherwise it is not valid.

We cannot implement this strategy in the case of infinitely many statements, since an algorithm, by definition, has a finite description. This is the hard part – being able to decide, for infinitely many statements, whether they are valid or not.
