Impossible Ona Turing Machine

From NonTuringComputing:

Problems that are computable by some definition, but not on a Turing machine. Problems soluble, therefore, by NonTuringComputing.

TransfiniteArithmetic
QuantumComputing Huh? Everything computable on a Quantum Computer is also computable on a TM.
An "always on" event handling system?

Problems involving transfinite numbers: requires "computable" to mean "a (provable?) theorem in a formal system"

If you say any statement is "computable" if by applying postulates to some set of axioms you can arrive at it (and thus, it is a theorem), then any mathematics dealing with TransfiniteNumbers? would certainly be computable but not on a Turing machine. Calculus, as in the Newtonian and Leibniz kind, involves infinities, so TuringMachines can only approximate it. -- SunirShah

By way of symbolic computation, e.g. the way Macsyma/Maxima do it, you can handle infinities, pi, and sin just fine. It's not like mathematics has some magic to deal with irrationals and infinities, it just doesn't put them through a lossy conversion. And neither need a Turing Machine do so either.

One could extend an existing model of computation with a new "primitive" that hallows the extended model to solve the halting problem. Examples:

Take a nondeterministic Turing machine and add "biased choice", i.e. the NTM will take path 1 if it terminates and path 2 if and only if path 1 does not terminate. Obviously, this extended Turing machine can solve the halting problem for an ordinary Turing machine.
Extended the Lambda calculus with a magical function B so that (B x) returns true if x diverges, false otherwise.
Take an ordinary programming language, and extend its equality operator so that it works on all functions in the following way: f = g if for every x, f(x)=g(x).

All these new operations effectively perform an infinite amount of work. The first one might actually be possible to implement with a QuantumComputer. -- StephanHouben

My pocket calculator seems to do calculus OK. It differentiates fine, does a lot of integrals too.

Calculus is algebra mashed together with infinity. Your calculator is not capable of finding sin(PI/3); it can only approximate it to some arbitrary precision. While this is normally sufficient, it becomes important to split hairs when you talk about NonTuringComputing. Running the approximation algorithm is within the bounds of TuringCompleteness, but solving the actual infinite series is not. However, it is within the realm of mathematics - using MathematicalInduction - to deal with such beasts. It's also possible to use Euclidean geometry and a number system defined by lengths of line segments. Hence the analog calculator bit. I suspect I'm still not being clear enough, a good sign I don't understand what I'm talking about well enough to explain it. I'll have to think about it. -- ss

It seems to me that you can simulate a FuzzyNeuralNet with a Turing machine, and a Turing Machine with a FuzzyNeuralNet. Since each can simulate the other, what then is the definition of NonTuringComputing? I had in mind that it must be something you can't do with a Turing machine. Would QuantumComputing be such a thing?

In order to be functionally equivalent, the TuringMachine cannot merely simulate a FuzzyNeuralNet. The system would really have to be a FuzzyNeuralNet. What I mean here is that the simulation of a neural net using (say) floating point numbers is not sufficient to be equivalent to an actual neural net. Floating point numbers lack the precision necessary to represent analog values precisely. An analog neural net is more complex (and a superset of complexity) of a TuringMachine because while you cannot implement an analog neural net with a TuringMachine, you can implement a TuringMachine with an analog neural net. -- SunirShah

Could you implement an analog neural net with a "Turing machine" in which each cell of the tape holds a single real number from the interval [0, 1)? It seems that you could, since you certainly can simulate a discrete neural net (where the weights are integers) on a Turing machine...

(This next para section may be redundant - anyone care to refactor and tidy?)

I know very little about this, but I have a thought, so I'll throw it out here and let others comment. I'm not sure why you can't 'simulate' a FuzzyNeuralNet on a TuringMachine. First of all, you CAN simulate my desktop machine with modern programming languages on a TuringMachine, so let's start with that. Now if I use the naive implementation, and use floats for my weights, then my FuzzyNeuralNet doesn't work. But most of the time the precise weights in the neural net don't matter. For instance, if you keep 2 places of accuracy, you can tell the difference between 1/2 and 2/3, but not between Sqrt(10) and Pi. So we don't use floats, we instead use a "RealNumber?" class which we have created. This class uses an approximation and proceeds through the computation (propagation through the FuzzyNeuralNet) until it encounters a calculation which is so closely balanced that the level of precision we saved isn't sufficient. Then we back-propagate and add additional levels of precision until the balanced calculation can be satisfied. If necessary, we backtrack again later.

This approach is not the most efficient in the world, but it seems unlikely to me (Note: NOT the same as proving it!) that the expected runtime diverges. And it doesn't address the limitation that the TuringMachine can only accept finite-precision inputs and only produce finite-precision outputs (although there are possible work-arounds for these too). But it seems to allow a TuringMachine to simulate a FuzzyNeuralNet.

-- MichaelChermside (PS: Please, WikiGnomes, help me reduce and simplify this thought.)

The StructureAndInterpretationOfComputerPrograms outlines a way to represent all "computable real numbers", somewhat along the lines of the RealNumber? class of MichaelChermside. First, we note that all real numbers can be represented as an infinite sequence of intervals [p_n, q_n], n=0,1,2,3,... , where p_n and q_n are rational numbers (which are trivially representable in a computer). Moreover, we require that the intervals nest, i.e. [p_n, q_n] is a subset of [p_m,q_m] if n > m. Finally, we require that p_n-q_n converges to 0 for n to infinity.

The real number r represented by such a sequence is the limit of the p_n's, or equivalently, the limit of the q_n's. Note that any rational number s can be represented by taking p_n=q_n =s, for all n.

Now the computable real numbers are all numbers for which this infinite sequence is computable, e.g. an algorithm exists for finding [p_n,q_n], given an arbitrary n. Such a computable real number can be represented as an infinite lazy stream of pairs of rational numbers, as done in the StructureAndInterpretationOfComputerPrograms.

We can now write algorithms for addition, multiplication, etc., but also for computing the sine, cosine, etc.. So unless you neural net has a very strange weighting function, it will be computable.

-- StephanHouben

The "very strange weighting function" is the key bit here. And that's why the AnalogNeuralNet? is a bad example. I'd guess that practically interesting neural nets can be simulated sufficiently precisely with a TuringMachine (or a desktop PC for that matter). But it is fairly straightforward to build AnalogNetwork?s that indeed have very strange weighting functions, namely such that do e.g. solve the hHaltingProblem. Or solve integrals in general.

The reason your pocket calculator can solve some (!) integrals only means that it has special case logic for an - admittedly - large class of integrals - but not all of them.

Or you could add PimcPiflPire to your instruction set.