FANDOM


Within hours of setting up our IRC channel ##googology, an interesting discussion occurred (edited for privacy and brevity):

[12:32:55] <FB100Z> Anyways, let's talk math
[12:33:15] <FB100Z> some dude is raving about "infinity-dimensional Turing machine" http://googology.wikia.com/wiki/User:65.26.80.144
[12:33:32] <Wojowu> I didn't even waste my time reading that
[12:33:46] <FB100Z> However it is actually an interesting idea if we put a TM in Hilbert space
[12:33:55] <Ikosarakt_> Why not, that's fun
[12:33:56] <FB100Z> and use ITTM instead of TM
[12:33:57] <Wojowu> It is
[12:34:18] <FB100Z> However we would need to revise the rules a bit
[12:34:26] <Wojowu> But how would ruleset work
[12:34:41] <Wojowu> We would have infinitely many ways to move
[12:34:46] <Wojowu> How to choose one?
[12:35:19] <FB100Z> We need a way to specify an arbitrary natural number, and have the TM move in that direction
[12:35:46] <FB100Z> the important thing is that this number must be specified at runtime
[12:36:08] <Wojowu> I don't really see how this is supposed to work
[12:36:20] <FB100Z> You could do something very, very clunky
[12:36:59] <FB100Z> In addition to L and R, the motion M reads the 1D tape along (x, 0, 0, ...)
[12:37:21] <FB100Z> and adds that vector to the TM's current position
[12:37:55] <FB100Z> it's a start, although it basically leaves the TM stranded after moving outside of the line :/
[12:38:16] <Wojowu> Hilbert space is uncountable, right?
[12:38:26] <FB100Z> I didn't use the right term
[12:38:54] <FB100Z> it's a countably infinite set of natural-number coordinate positions
[12:39:08] <FB100Z> equivalent to Bowers' X^X space
[12:39:08] <Wojowu> Okay
[12:39:15] <Wojowu> I see
[12:39:42] <Wojowu> So only finitely many coordinates can be nonzero
[12:39:45] <Wojowu> At a time
[12:39:51] <FB100Z> Right.
[12:40:07] <FB100Z> But if we use ITTM instead of TM...
[12:42:33] <Wojowu> ...then we have no control over how many coordinates are finite
[12:42:53] <Wojowu> *are nonzero
[12:43:09] <FB100Z> How come?
[12:43:30] <Wojowu> Well, using your idea of adding vectors
[12:43:42] <Wojowu> Machine can write infinitely many ones
[12:43:45] <Wojowu> And boom
[12:44:33] <FB100Z> what are the consequences of that?
[12:44:56] <Wojowu> Then we are working in uncountable Hilbert space
[12:45:13] <FB100Z> Sure.
[12:45:26] <Wojowu> Okay, so it's not a problem
[12:45:33] <FB100Z> However it seems we can only access countably many positions in the Hilbert space
[12:45:54] <FB100Z> because there are countably many rules that can lead up to the M motion
[12:46:48] <FB100Z> In other words, at all points the machine's position vector must be somehow computable with ITTMs, I believe :(

...

[13:10:05] <FB100Z> Regarding Hilbert ITTMs
[13:10:27] <FB100Z> although exploring higher-order spaces is interesting, I hypothesize that it ultimately gets us nowhere
[13:10:46] <Deedlit11> Hilbert ITTMs?
[13:10:47] <Wojowu> Yeah
[13:11:05] <Wojowu> The idea is this
[13:11:27] <Wojowu> We have an ITTM with one tape head and other head inside a Hilbert space
[13:11:52] <Wojowu> We now use the tape to specify where we move Hilbert space head
[13:12:11] <Wojowu> I think it's clear where this is going
[13:12:22] <FB100Z> so the colors in the 1D tape encode a vector that gets added to the Hilbert head's position
[13:13:23] <FB100Z> it's important that the machine is infinite-time, so we can access positions with infinitely many nonzero coordinates
[13:13:37] <Deedlit11> so we are talking about Z^Z rather than a Hilbert space really
[13:13:45] <FB100Z> yeah, I didn't quite know what to call it
[13:13:48] <Wojowu> Actually, yeah
[13:13:58] <Deedlit11> or 2^Z
[13:14:02] <Wojowu> It's a discrete subset of Hilbert space
[13:14:48] <Deedlit11> sounds interesting
[13:15:08] <FB100Z> despite the fact that the larger space is uncountable, I think that we can only access countably many positions
[13:15:38] <FB100Z> due to ITTM rules being countable
[13:15:43] <Deedlit11> right
[13:15:54] <Wojowu> But it'll be hard to keep track of which positions have been visited and which haven't...
[13:16:10] <FB100Z> which leads me to suppose that ultimately this is computationally equivalent to ITTMs
[13:16:32] <Wojowu> I think that's correct, although it's not that obvious

...

[13:24:22] <Wojowu> Guys!
[13:24:26] <Wojowu> We were wrong!
[13:24:35] <Wojowu> This model actually is stronger!
[13:24:44] <FB100Z> Wait whaaaaat
[13:24:52] <Wojowu> Let me modify it a bit:
[13:24:53] <Deedlit11> waaat
[13:25:00] <Wojowu> We have two tapes, scratch and control
[13:25:18] <Wojowu> Scratch does what it does, control tape controls head in Hilbert space
[13:25:33] <Wojowu> So now suppose we do the following:
[13:25:44] <Wojowu> We simulate some machine M on scratch tape
[13:26:12] <Wojowu> On control tape we write instantaneous description of M at every step
[13:26:22] <Wojowu> And we move to that position in Hilbert space
[13:26:26] <Wojowu> And flash that cell
[13:26:48] <Wojowu> If configuration repeats infinitely many times, this flag will flash infinitely many times
[13:26:59] <Wojowu> And will ultimately end up being on
[13:27:07] <Wojowu> So if this configuration happens one more time
[13:27:11] <Wojowu> We can see that
[13:27:15] <Wojowu> This way
[13:27:21] <Wojowu> We can solve halting problem!
[13:27:30] <FB100Z> Huh. Let me process that a bit.
[13:27:41] <Wojowu> Because machine doesn't halt iff some it's configuration repeats w times
[13:27:53] <Wojowu> *its
[13:28:17] <FB100Z> Scratch is the Z^Z head, right?
[13:28:34] <Wojowu> No, scratch is another linear tape
[13:28:39] <Wojowu> I modified model a bit
[13:28:47] <Wojowu> So we have to linear tapes and Hilbert space
[13:28:54] <Wojowu> But this can also work on one tape

...

[13:29:29] <FB100Z> If you're right that it is stronger, then the following extension should also work:
[13:29:43] <FB100Z> using the Hilbert heads to control vectors in even larger Hilbert spaces
[13:30:10] <Wojowu> It's hard for me to imagine this
[13:30:17] <Wojowu> But I guess it might work too
[13:30:27] <FB100Z> Yeah, I can't really wrap my had around anything of cardinality Beta_2 either :(
[13:30:31] <FB100Z> *head

...

Say cheese!

This is a proposal for a highly experimental Hilbert-space ITTM. I call it a "photographic ITTM."

PhITTMs have two tapes. One is the control tape, which is an ordinary one-dimensional two-color tape. The other is a photo tape, which is essentially a function \((\mathbb{Z} \mapsto \{0, 1\}) \mapsto \{0, 1\}\). The control tape's head behaves like any other ITTM, but the photo tape's head is a bit different. At each step, the photo head jumps to the position determined by treating the control tape's colors as a vector.

The transition function is as follows:

(state, control color, photo color) → (new state, new control color, new photo color, control motion)

As usual, at each limit state, all control and photo cells are set to the limit superior of their previous colors.

Intuitively, the photographic ITTM can be thought of as an ITTM that can take a "photo" of its tape and store this in an album. At each step, the ITTM can check whether its current tape matches a photo in the album. It also has the options of taking a photo of its current tape or erasing it. At each limit stage, a photo in the album is retained iff it existed for an unbounded amount of time up to that point.

Note that state is not included in the photo. I don't know whether inverting this rule has any effect.

Why not photographic TMs?

If we apply the camera to ordinary TMs, it's not hard to see that the result offers no additional power. A photographic TM can be simulated by an ordinary TM — the album only requires finite memory, and comparing the tape to a photo is a decidable problem.

Imagine our surprise when Peng found a convincing (although not yet confirmed) argument showing that PhITTMs can solve the halting problem for ITTMs. We both suspect that they are computationally equivalent to one of the ITTM oracles.

Yo dawg

Even more experimentally, we can add another photo tape whose head is located according to the colors of the first photo tape, and of course we can continue adding more and more photo tapes. I think they can even be extended into an ordinal hierarchy, where another control tape is used to index the photo tape you want to read from.

We don't know whether any additional power is gained by these additions, and the ordinal hierarchy is especially speculative. But it's fun to imagine these things.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.