3 ms·
Their proof depends on arbitrary precision and they explicitly state that the finite case is not TC. But if you are talking about arbitrary precision floats, o
by nyrikki 3y ago
Their proof depends on arbitrary precision and they explicitly state that the finite case is not TC.
But if you are talking about arbitrary precision floats, or the computable set of the reals it is equivalent.
The computable reals are just the concatenation of the natural numbers/ints
So it is the countable infinity and thus the cardinality of Aleph-nought.
That adds to the time complexity, while the unbounded memory requirement comes from the definition of a Turing machine which is roughly a finite state machine+ an infinite tape.
As the reals are uncomputable almost everyplace, you would need an activation function that only produced computable reals, as they are equivalent rational activation functions are simpler for the proof.