2
$\begingroup$

Introduction

Hello, I'm designing a generalized model of Turing machines for a formalization in MIZAR. Mizar needs some concrete objects to work with, so I spent some time figuring out how the "tape" of a Turing machine could be defined since that part is usually left out when introducing Turing machines.
After some thinking I concluded it would be best to use graphs, so I define a "Turing Space" $T$ as a function from an cardinal $C$ to graphs. A position $p$ in the Turing Space is then defined as a function from the cardinal into the vertex sets of these graphs, so that for $c\in C$, $p.c$ is a vertex of $T.c$. From this basis one can built transition functions and so forth.

Examples

Given a double ray (a path graph that is infinite in both directions) $R$ and a positive integer $k$, the function $f_k:k\ni i\mapsto R$ (defined on $\{0,\ldots,k-1\}$) would be a Turing space describing the bands of a $k$-band TM.
Given a positive integer $d$, set $E_d:=\{\{a,b\}:a,b\in\mathbb{Z}^d,\sum|a_i-b_i|=1\}$ and graph $G_d=(\mathbb{Z}^d, E_d)$, this is the grid on $\mathbb{Z}^d$. Now the function $g_d:\{0\}\ni i\mapsto G_d$ describes the hyperspace of a $d$-dimensional TM.
These two examples are of course quite different, as the first has $k$ pointers, that can move in 3 directions (left, right, stay) each, and the second has one pointer that can move in $2d+1$ directions. That they are nevertheless computational equivalent (because they are Turing-complete) is well known. Also both reduce to a simple Turing tape in case of $k=d=1$.
It is easy to see that other well-known tape variants can be described by this definition just as well.

But it doesn't end there

However, the definition above allows much more complex examples for tapes, most notably when using infinite cardinals. And when I'm about defining Turing machines, I wonder why I would restrict the alphabet and set of states to be finite. Of course, these generalizations make it much more difficult to image any kind of realization in the real world. Nevertheless, I think it is kind of interesting if these generalizations of a TM would make it possible to archive something beyond Turing completeness. Other known generalizations such as non deterministic TMs and quantum TMs do not seem to have archived greater computability. Maybe I missed something?

The Question

Has my kind of generalization (the different "Turing Spaces") been studied before? Or any kind of allowing infinite states and/or alphabets besides the kind appearing in quantum TMs?

$\endgroup$
  • $\begingroup$ Your description is too cryptic for me to understand. What is $f_k : k \ni i \mapsto R$ supposed to mean? $\endgroup$ – Andrej Bauer Dec 27 '17 at 21:15
  • 1
    $\begingroup$ I've no idea what MIZAR is but why can't you just formalize the tape as a finite sequence, as usual? $\endgroup$ – David Richerby Dec 27 '17 at 21:35
  • $\begingroup$ @DavidRicherby Has been done already: mizar.org/version/current/html/turing_1.html#NM2 It is simply too narrow to capture advanced concepts like $k$-band TMs or $d$-dimensional TMs. And since Mizar is a formalization system, this means the definitions have to be done again and again for these generalized, yet specialized cases. Hence an even more general approach is desirable. At first I thought of connected subsets of the grid of $\mathbb{Z}^d$ to be used as Turing Spaces, but then I realized the important thing are cells and how they are connected. So graphs, yeah. $\endgroup$ – SK19 Dec 29 '17 at 11:06
  • $\begingroup$ @AndrejBauer Sorry for the inconvenience. $f_k$ maps from $k=\{0,\ldots,k-1\}$ (ordinal viewpoint of natural numbers) to the set $\{R\}$, i.e. it is the constant function $f_k\equiv R$. But I thought if I wrote that, the domain would be unclear. Also I thought that the $x \mapsto f(x)$ notation for a function $f$ and an element $x$ from its domain would be commonly known. $\endgroup$ – SK19 Dec 29 '17 at 11:13
3
$\begingroup$

A general notion of machines based on graphs was given by Wilfried Sieg and John Byrnes in K-Graph Machines: Generalizing Turing's Machines and Arguments. It may or may not be related to what you are doing.

Also note that it is quite easy to find a complete formalization of Turing machines. Why are you saying that "the tape of a Turing machine ... is usually left out when introducing Turing machines". That's an odd thing to say. Let's perform an experiment. For instance, what is unclear about the definition given on Wikipedia (following a standard textbook)? All you need is a formalization of finite sequences, and I'd be flabbergasted if Mizar hasn't got those.

$\endgroup$
  • $\begingroup$ That description doesn't actually talk about the tape itself. But as you say, it is not hard to provide a formalization. I recently wrote a symbolic definition of a (alternating) Turing machine and simply represented the tape, for the purposes of defining acceptance, as a function $\mathbb N\to\Gamma$, $\Gamma$ being the set of symbols. $\endgroup$ – Derek Elkins Dec 28 '17 at 8:32
  • $\begingroup$ @DerekElkins When I define the tape as a function from a domain to $\gamma$, then I did not define the tape, but the tape and what's written on it. The tape is represented by the domain. Tying the domain to a specific set may be good for practical cases, but e.g. taking $\mathbb{Z}^d$ could be the domain for both the $d$-dimensional and the $d$-band TM, then I need to make distinction how the head(s) move(s). I'm trying to avoid exactly that: too many distinctions. Instead, I'm trying to create an all-purpose formalization and am just wondering if the new cases appearing have been studied yet. $\endgroup$ – SK19 Dec 29 '17 at 11:27
  • 1
    $\begingroup$ @SK19 In that case, I would take a more "axiomatic"/"abstract" approach. Instead of trying to pick a "most general" representation, avoid picking any representation. For example (just a random idea I thought up just now which is probably terrible), maybe it makes sense to have the transition function return the generators of a group, and the tape is a set acted upon by that group (and it's values are just a function from the set to the alphabet). 1D 1-sided is $\mathbb Z$ acting on $\mathbb N$. 2D is $\langle U,R\mid UR=RU\rangle$ acting on $\mathbb N\times \mathbb N$. $\endgroup$ – Derek Elkins Dec 29 '17 at 11:36
  • 1
    $\begingroup$ @SK19 My point being instead of making it so that specific examples can be encoded into your formalization, make it so that specific examples are instances of your formalization. $\endgroup$ – Derek Elkins Dec 29 '17 at 11:39
  • 2
    $\begingroup$ @SK19: the difference between an abstract and a general concrete approach is that the abstract approach does not prescribe a specific representation. You are fixing the representation of the tapes to involve certain kinds of graphs and maps into them, etc. An abstract approach would not do such a thing. Instead, you'd have an (arbitrary) set $T$ for "tapes" and some operations on $T$ (which may or may not be a group action). In an abstract approach it doesn't matter what $T$ "really is". $\endgroup$ – Andrej Bauer Dec 29 '17 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.