Cannot understand a mapping function which include some sets

38 Views Asked by At

I have kept a screenshot of my problem below which describes about the various sets. At the last line, there is an expression where a function delta uses those sets and maps them into another. I am not able to understand the meaning/relevance of symbols like \, X in that expression.

image

2

There are 2 best solutions below

1
On BEST ANSWER

Recall that $X\setminus Y=\{x\in X\mid x\notin Y\}$.

The last line says that $\delta$ is a function with takes pairs $(q,\gamma)$ such that $q\in Q\setminus\{q_Y,q_N\}$ and $\gamma\in\Gamma$, and its result is a triplet $(q',\gamma',i)$ where $q'\in Q,\gamma'\in\Gamma$ and $i\in\{-1,1\}$.

4
On

As I mentioned in the comment (or see Asaf Karagila's post), "$\backslash$" indicates set difference.

However, if your question was what is the significance of the set difference appearing in the definition of the transition function for Turing machines, I can also elaborate a bit:

I assume the $q_Y$ and $q_N$ refers to something like the accept and reject state. The transition function intuitively tells the Turing machine what do next depending on its currently configuration. The current configuration consist of the symbol currently being read by the Turing machine and the state of the Turing machine. However, the convention is that if the Turing machine reaches (if ever) the accept or reject state, the Turing machine halts. Hence in the definition of the transition function, one has $Q \backslash \{q_N, q_Y\}$ in the domain of the transition function since the Turing machine is not suppose to do anything in the $q_Y$ or $q_N$ state.


I added a somewhat trivial example. (Note there are different conventions for Turing machine like whether the reading head can stay put, blank symbols, initial tapes, etc. I hope the basic ideas have been conveyed):

Let $\Gamma = \{0,1, B\}$ and $Q = \{q_I, q_Y, q_N\}$, where $q_I$ is the distinguished initial state and $B$ represents a blank symbol. Instead of $\{-1, 1\}$, I will use $\{L, R\}$ to denote "move left" and "move right".

Let $\delta : \{q_I\} \times \{0,1\} \rightarrow \{q_I, q_Y, q_N\} \times \{0,1\} \times \{L, R\}$ be defined as follows:

$\delta(q_I, 0) = (q_I, 0, R)$

$\delta(q_I, 1) = (q_N, 0, R)$

$\delta(q_I, B) = (q_I, 0, R)$

It is easy to check that the Turing machine with this associated transition function will behave as follows: if it read a $0$ or a blank, it will keep the input and move to the right on the tape. If it hits a $1$, then then the Turing machine will write over it with a $0$ move to the right and reject (and hence halt).

Note for example, this Turing machine will run forever on any input without any $1$'s.