Нейронная сеть эквивалентна машине тьюринга (т.к. на МТ можно построить эмулятор НС, а на НС можно построить эмулятор МТ).
НС приписывают "мистические" способности из-за того, что НС может выполнять действия, которые не закладывались в нее напрямую "программистом". Но такими способностями обладает большое кол-во алгоритмов (а не только НС), в частности, любые алгоритмы которые перестраивают свою управляющую логику на основе обратной связи.