0
$\begingroup$

as the title says does having a mutable transition function make the Turing machine more powerful

by mutable I mean we have a set of transition functions that we can choose one of them arbitrary based on the current state and symbol

in definition of Turing machine from wikipedia instead of $\delta$ we have

a set $\Delta = \{\delta_1, \delta_2, \delta_3, ..., \delta_n\} $ that is a subset of all possible transition functions and

$O = \{o_1, o_2, o_3, ...\}$ where $o_i = \delta_j$

$\delta : \mathbb{N} \rightarrow O$

$\delta(i) = o_i$ is the actual transition function and $o_i$ is defined for current state and symbol and machine start from $\delta(1)$ and then $\delta(2),\delta(3),...$

$\endgroup$
15
  • 2
    $\begingroup$ How does "choosing a transition function arbitrarily based on the current state and symbol" differ from the normal operation of a Turing machine, which looks chooses its transition function based on the current state and symbol? By what means should we measure the quality of being "powerful"? $\endgroup$
    – DMGregory
    Commented Oct 24, 2021 at 22:31
  • $\begingroup$ transition functions could have a different value for current state and symbol, by powerful I mean can it solve the Halting Problem $\endgroup$
    – user70365
    Commented Oct 24, 2021 at 22:43
  • $\begingroup$ A Turing machine can already select a distinct transition for every combination of state and symbol, so I'm not sure what change you have in mind. Try editing your question to walk us through the operation of such a "Raoof Machine" in detail. Show how you would specify its transitions, and how a simple machine definition would operate on a simple input tape, so we can see where it departs from Turing's definition. $\endgroup$
    – DMGregory
    Commented Oct 24, 2021 at 23:57
  • 4
    $\begingroup$ How is changing to another transition function different from adding another set of states? $\endgroup$
    – greybeard
    Commented Oct 25, 2021 at 6:36
  • 2
    $\begingroup$ A TM that mutates its own transition table (if that's what you mean) is not more powerful, because you can simulate it on a tape of another TM. $\endgroup$ Commented Oct 25, 2021 at 11:32

2 Answers 2

0
$\begingroup$

First, let's simplify your definition of a "hyper-Turing machine".

A hyper-Turing machine is a 7-tuple $M = (Q, \Gamma, b, \Sigma, \delta, q_0, F)$, where

  • $\Gamma$ is a finite set of tape alphabet symbols
  • $b \in \Gamma$ is the "blank symbol"
  • $Q$ is a finite set of states
  • $\Sigma \subseteq \Gamma \setminus \{b\}$ is a finite set of input symbols
  • $q_0 \in Q$ is the initial state
  • $F \subseteq$ is a finite set of "accepting states"
  • $\delta : \mathbb{N} \times (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \{L, R\}$ is the "transition function"

Note that in OP's original question, we instead had some finite set $\Delta \subseteq (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \{L, R\}$ and some function $\delta : \mathbb{N} \to \Delta$. However, without loss of generality, we can always take $\Delta = (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \{L, R\}$, since this set is finite. Then we have $\delta : \mathbb{N} \to (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \{L, R\}$, but by Currying, this is equivalent to $\delta : \mathbb{N} \times (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \{L, R\}$.

The semantics are that the hyper-Turing machine keeps track of the number of transitions it has made so far. If the machine has made $n$ transitions so far, the symbol at the head is $v \in \Gamma$, and the current state is $q \in Q \setminus F$, then let $(q', x', d) = \delta(n, q, v)$. The Turing machine first replaces the character at the head location with character $v$. It then moves the head in direction $d$. It then transitions to state $q$.

It turns out that

Thm. Any function $\mathbb{N} \to \mathbb{N}$ can be computed by a hyper-Turing machine.

What does it mean for a function $f : \mathbb{N} \to \mathbb{N}$ to be computed by a hyper-Turing machine $M$? It means that there is some hyper-Turing machine over input alphabet $\Sigma = \{1\}$ such that for all $n \in \mathbb{N}$, if the hyper-Turing machine is run on input $1^n$, then the Turing machine eventually halts, and when it halts, the tape has $1^{f(n)}$ on it.

Proving this is quite simple. Simply consider the following pseudocode:

For each $i \in \mathbb{N}$:

1: Walk $i$ steps to the right. Then, walk $i$ steps back to the left. From this information, we know whether the string is $1^i$. 2: If the string is $1^i$, then erase the string, write the string $1^{f(i)}$, and halt, taking a total of $i + f(i)$ steps. Otherwise, simply walk back and forth for a total of $2 \cdot (i + f(i))$ steps, then continue with the loop.

So all functions $\mathbb{N} \to \mathbb{N}$ are hyper-Turing computable. Using a bit more creativity, it's possible to extend the original argument to show that given any alphabet $\Sigma$, all functions $\Sigma^* \to \Sigma^*$ are hyper-Turing computable. This, of course, involves pushing across the bijection $\mathbb{N} \to \mathbb{N}$, though it requires a bit more creativity than the last case.

So all functions are hyper-Turing computable. Hence, hyper-Turing computability is a rather useless notion.

$\endgroup$
5
  • $\begingroup$ thank you for your answer but I'm not sure that I understand your useful/useless distinction $\endgroup$
    – user70365
    Commented Nov 1, 2021 at 9:36
  • $\begingroup$ @raoof Useless in the sense that there's little mathematical point in analysing "hyper-Turing computable" functions, since all functions are hyper-Turing computable. $\endgroup$ Commented Nov 1, 2021 at 20:16
  • $\begingroup$ if you believe that non-computable function does not exist you can say the same thing for Turing Machines: all computable function are TM computable $\endgroup$
    – user70365
    Commented Nov 2, 2021 at 3:10
  • $\begingroup$ @raoof This is not true. If you believe that all functions are computable, Turing machines are incredibly useful because they allow one to encode sequences as natural numbers. You can’t even form the statement “all functions are computable” without first defining “computable”. $\endgroup$ Commented Nov 2, 2021 at 5:53
  • $\begingroup$ I think we disagree about what functions means, for me a function means a process realizable in nature so the question is: are all realizable processes in nature are TM computable? if you think yes then you don't believe in non-computable function $\endgroup$
    – user70365
    Commented Nov 2, 2021 at 6:19
0
$\begingroup$

Having a transition function of transition functions is the same thing as having a single transition function.

Fix an alphabet $\Sigma$ and a set of states $S$. A transition function on $S$ is a map $S \times \Sigma \to S$.

You are proposing to use $n$ transition functions \begin{align*} \delta_1 &: S \times \Sigma \to S \\ &\vdots \\ \delta_n &: S \times \Sigma \to S \\ \end{align*} together with a "meta-transition" function $\tau$ which takes as input the index $i$ of the current $\delta_i$, a state $s \in S$ and a symbol $a \in \Sigma$, and returns the next index $j = \tau(i, s, a)$ so that next time we use $\delta_j$.

The above information is equivalent to a single transition function $\bar{\delta} : \bar{S} \times \Sigma \to \bar{S}$ where we now use as the state set $$\bar{S} = \{(i, s) \mid 1 \leq i \leq n \land s \in S\}$$ and define $$\bar{\delta}((i,s), a) = (\tau(i,s,a), \delta_i(s,a)).$$ That is, it makes no difference to say that the $i$-th transition function $\delta_i$ was used in state $s$ and to say that $\bar{\delta}$ was used in the combined state $(i,s)$.

$\endgroup$
6
  • $\begingroup$ you misread my question, my "meta-transition" function accept the current step as input not the index of current transition function $\endgroup$
    – user70365
    Commented Oct 31, 2021 at 14:22
  • $\begingroup$ Your question is quite unclear, it has sensless things such as "$o_i = \delta_j$", so I am not going to try to guess how to make sense of it it beyond what I have already invested. In any case, the important bit about the answer is the idea that you can replace several transition functions with a single one by changing the set of states. You're welcome to adapt it to whatever you have in mind. $\endgroup$ Commented Oct 31, 2021 at 19:22
  • $\begingroup$ P.S. The word "step" does not appear in your question. $\endgroup$ Commented Oct 31, 2021 at 19:22
  • $\begingroup$ Ah, in the comments science fiction is brought in and some "steps" and infinite loops are mentioned. There's nothing further for me to say here. $\endgroup$ Commented Oct 31, 2021 at 19:24
  • 1
    $\begingroup$ It occurs to me that you might be interested in hypercomputation and Infinite-time Turing machines. $\endgroup$ Commented Nov 1, 2021 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.