Infinite State Machine

A computational machine whose complete description is inextricably linked to a description of the universe. For example, an interferometer. Or a flower. Or a person.

--PeterMerel

An infinite state machine can be conceived but is not practical. --A Cretan InfiniteStateMachine

Another way of stating this is that the only known InfiniteStateMachine is the universe. And we're not really sure about it being infinite. -- MichaelSparks

I'm pretty sure an infinite state machine is simply a state machine with an uncountable number of states and transitions. "Uncountable" doesn't mean "the size of the universe". It just means we don't know. An example of an ISM might be a stock price simulation tree. In general an ISM can be thought of or illustrated as a binary decision tree for any organization, system, or algorithm which undergoes runtime modification and/or has no finite end state. I think most real-world general purpose computing systems are probably ISMs. -- SteveTraugott?

No, InfiniteStateMachine is a StateMachine that doesn't have a finite number of states (whether we know how many or not).

Actually there is a very nice proof that any finite volume of space contains only a finite amount of information, with a maximum that is in fact a function of that volume. Coupled with the limitation of the speed of light on information exchange, what it comes down to is that it pretty much will never make much difference to our part of the universe whether the rest of the universe contains infinite information or not. The universe can for most purposes be treated as containing a finite amount of information, because it does so within any finite volume.

It is, in particular, irrelevant to arguments about TuringMachines to discuss whether the universe is infinite or not. If you want a TuringMachine with an uncountably infinite number of tapes each containing an uncountably infinite amount of information, which can also perform an uncountably infinite number of operations per tape-step, that's just fine, that can be dealt with mathematically -- but that's not a question of physics.

Conversely, even quantum computers cannot perform infinite calculations in finite time within a finite volume of space. So that's all barking up the wrong tree. -- DougMerritt

Actually there are several apparently physically realizable models of HyperComputation? on the books. Some use relativistic effects, some QM. Cf especially http://arxiv.org/pdf/quant-ph/0203034 , which officially blew my mind.

Now I'd sure like a URL for the proof you mention above. In its absence I can only offer questions. Given the plentiful evidence we have for NonLocality, how do you define your finite volume of space? What about information encoded in its distinction from the rest of space? Isn't the volume of a region of space dependent on relativistic frame? What if the volume contains a white hole? Does your proof refute Everett's notoriously space-wasteful interpretation of QM? Given Shannon's definition of a bit as a quantity of information that halves the uncertainty of a situation, does your proof have a problem with Heisenbergian complementarity? Can you bound the exformation of your region of space - surely as important to describing its empirical state as its information content ... --PeterMerel

Nevertheless I give you this. I once gave a demonstration that there exists a set of laws of physics that would permit the construction of a kind of hypercomputer that had the ability to solve the halting problem for both the Turing machine and itself. At the time I gave the demonstration, I believed the laws of physics that corrispond to our universe to disallow such a construction. However, I have since realized that it is in fact an open problem in physics as to whether or not the same construction is possible in this universe.

The key piece seemed to be that the simple contradiction proof that the self-halting problem is unsolvable involves the man who would disprove inspecting the machine's language so as to write the contradiction. My response was to give the machine a constructor that would permit it to build a more powerful hypercomputer to match the required ability to solve the problem. The final result is a computer that can solve Turing's halting problem but its own halting problem is in fact trivial: it can compute any boolean function in a finite time.

The physical setup involves a negative energy bubble that uses inverse time dilation to permit the computation of an infinite steps in a finite time from the perspective of an outside observer. You will forgive me that I lost my reference, but this was cited work. My own extension was to arrange for the alternate laws of physics that would permit the construction of another bubble inside the first (and so on to infinite depth) at the will of the executing machine. The consequence is the halting problem can be defeated by outraising it.

I once thought that our own laws of physics would exclude any such construction; however the naked ring singularity (naked singularities are no longer excusable as a way to construct one has been published) provides for the existence of an infinite space with similar properties. Whether or not this construction is excluded remains to be seen. --JoshuaHudson

"The physical setup involves a negative energy bubble that uses inverse time dilation to permit the computation of an infinite steps in a finite time from the perspective of an outside observer."

How much weed do you have to smoke for that to make any sense?

None. General relativity has always had strange solutions with exotic matter. Some of them have worse consequences than this one.

[It's an incomplete analysis. There is a maximum amount of energy and information in any bounded volume - the 'bubble'. So, first of all, you'd be limited to the subset of computations that run in finite space. Second, in general, computations are not reversible processes. They lose information, with a corresponding increase in entropy and heat. It takes a continuous feed of energy to keep computations running, and a corresponding amount of cooling. The rate of computation within the bubble would ultimately be limited by the rate of energy transfer, which is not likely to be infinite.]

Thank you. While that was a non-issue for the custom laws of physics (set second law = OFF), that would almost certainly limit the ring singularity setup.

References: http://clublet.com/c/c/why?ThereIsNoInfinity