Предложение$\,$2. Задача проверки для произвольной заданной системы вида $(\ref{i2m})$ наличия у нее решения в $K((x))^m\setminus \{0\}$ алгоритмически неразрешима. Алгоритмически неразрешима и задача проверки полноты ранга данной системы.
Доказательство. Назовем сигналом последовательность, заданную некоторым алгоритмом $\omega,$ вычисляющим для каждого $i=0,1,\dots$ значение $\omega(i) \in \{0,1\},$ при этом
– $\omega(0)=1,$
– если $\omega(i)=0$ для некоторого $i\geqslant 1,$ то $\omega(i+1)=0.$
Задаваемый алгоритмом $\omega$ сигнал назовем бесконечным, если $\omega(i)=1$ для всех $i\geqslant 0,$ и конечным в других случаях.
Задача алгоритмической проверки бесконечности сигнала неразрешима: любую последовательность $c(0), c(1), \dots $ можно алгоритмически преобразовать в сигнал $\omega _c,$ который будет конечным, если и только если исходная последовательность $c(n)$ содержит хотя бы один нулевой элемент: полагаем $\omega_c(i)=0,$ если среди элементов $c(0),\dots, c(i)$ найдется хотя бы один нулевой. Если бы была возможна алгоритмическая проверка конечности произвольного сигнала, то была бы возможна и алгоритмическая проверка наличия нулевого элемента в данной последовательности. Но такая проверка невозможна в силу упоминавшегося результата Тьюринга.
Используя доказанное, мы можем установить алгоритмическую неразрешимость задачи проверки обратимости данной ненулевой квадратной матрицы с элементами в $K((x)).$ Пусть $\omega$ является произвольным сигналом. Матрица $$A=\left({\begin{array}{cc} 1-x&1\\ 1&\sum_{i=0}^\infty \omega (i)x^i\end{array}}\right)$$ обратима, если и только если сигнал $\omega$ конечен, а в случае бесконечного сигнала ее определитель равен нулю: $(1-x)(1+x+x^2+\dots)-1=0.$ Следовательно, система линейных алгебраических уравнений $As(x)=0$ имеет ненулевое решение $s(x)=(s_1(x), s_2(x))^T,$ если и только если сигнал $\omega$ бесконечен. Система $$\left({\begin{array}{cc} 1-x&1\\ 1&1+x+x^2+\dots\end{array}}\right)s(x)=0,$$ обладает ненулевым решением $s(x)=(s_1(x), s_2(x))^T=(-1,1-x)^T.$ Теперь покажем, что задача проверки наличия у данной системы решения в $K((x))^m\setminus \{0\}$ алгоритмически неразрешима. Положим $B=\left(\begin{array}{cc} x&0\\ 0&x\end{array}\right).$ Пусть $\omega$ — некоторый сигнал. Система $$ AB \theta y(x)+Ay(x)=0,$$ c рассматриваемой матрицей $A$ имеет решение в ${K((x))^2\setminus \{0\}},$ если и только если сигнал $\omega$ бесконечен: если сигнал конечен, то матрица $A$ обратима, и данная система эквивалентна системе $$\left(\begin{array}{cc} x&0\\ 0&x\end{array}\right)\theta y(x)+\left(\begin{array}{cc} 1&0\\ 0&1\end{array}\right)y(x)=0,$$ которая не имеет ненулевых решений в $K((x))^2.$ В самом деле, эта система состоит из двух уравнений: $$x\, \theta y_1(x)+y_1(x)=0,\;\;x\, \theta y_2(x)+y_2(x)=0,$$ и никакая ненулевая константа не является решением первого уравнения, а если $y_1(x)\neq 0,$ то $\val x\,\theta y_1(x)\geqslant 1+\val y_1(x)$ (обосновывается рассмотрением случаев равенства и неравенства нулю значения $\val y_1(x)$). Равенство ${x\,\theta y_1(x)=-y_1(x)}$ может выполняться только при $y_1(x)=0.$
Но если $A$ необратима, то у $ AB \theta y(x)+Ay(x)=0$ имеется решение в $K((x))^2\setminus \{0\}.$ Система $$\left(\begin{array}{cc} x&0\\ 0&x\end{array}\right)\theta y(x)+\left(\begin{array}{cc} 1&0\\ 0&1\end{array}\right)y(x)=\left(\begin{array}{cc} s_1(x) \\ s_2(x) \end{array}\right)$$ с $s_1(x)=-1, s_2(x)=1-x$ имеет решение $\left( -1, 1-\frac x2\right)^T.$ Результат умножения обеих частей этой последней системы на матрицу $A$ позволяет заключить, что ее любое решение является также решением системы $AB \theta y(x)+Ay(x)=0.$
Итак, система $AB \theta y(x)+Ay(x)=0$ имеет ненулевое лораново решение, если и только если сигнал $\omega$ бесконечен. Любой алгоритм проверки наличия ненулевых лорановых решений систем подобного вида мог бы быть использован для проверки бесконечности произвольного сигнала. Но, как нами установлено, такая алгоритмическая проверка невозможна.