Skip to main content
added 179 characters in body
Source Link
Narek Bojikian
  • 4.7k
  • 1
  • 12
  • 36

The way each variable is represented is a matter of encoding of the problem and the machine does not have to assign an independent symbol for each variable. Your question is similar to, we can not represent all graphs in a turning machine since for a fixed alphabet $\Sigma$ we can set the number of vertices to $\Sigma + 1$. Well, we can represent each variable of sat, or each vertex in the graph using a binary number. Hence, a machine whose input and working alphabet is zero and one can represent any graph or Boolean formula. Note that any turningturing machine can be translated to a turning machine over the binary language on the expense of a constant factor of the time and the place complexity using the following trick.

Let $1, 2, 3, \dots n$ be an enumeration of the elements of the alphabet. Let $m = \left\lfloor \log n \right\rfloor + 1$. Change each symbol with a word of length $m$ in the machine, where the $i$th syboldsymbol turns into $\mathrm{bin}(i)$ prefixed with zeroes to reach length $m$. The machine reads the letters in blocks (you can save what word you are reading now in the state of the machine).

Note. The way a machine encodes the input can have a big effect on its time and place complexity note the adjacency lists and adjacency matrices representations of graphs.

The way each variable is represented is a matter of encoding of the problem and the machine does not have to assign an independent symbol for each variable. Your question is similar to, we can not represent all graphs in a turning machine since for a fixed alphabet $\Sigma$ we can set the number of vertices to $\Sigma + 1$. Well, we can represent each variable of sat, or each vertex in the graph using a binary number. Hence, a machine whose input and working alphabet is zero and one can represent any graph or Boolean formula. Note that any turning machine can be translated to a turning machine over the binary language on the expense of a constant factor of the time and the place complexity using the following trick.

Let $1, 2, 3, \dots n$ be an enumeration of the elements of the alphabet. Let $m = \left\lfloor \log n \right\rfloor + 1$. Change each symbol with a word of length $m$ in the machine, where the $i$th sybold turns into $\mathrm{bin}(i)$ prefixed with zeroes to reach length $m$. The machine reads the letters in blocks (you can save what word you are reading now in the state of the machine).

The way each variable is represented is a matter of encoding of the problem and the machine does not have to assign an independent symbol for each variable. Your question is similar to, we can not represent all graphs in a turning machine since for a fixed alphabet $\Sigma$ we can set the number of vertices to $\Sigma + 1$. Well, we can represent each variable of sat, or each vertex in the graph using a binary number. Hence, a machine whose input and working alphabet is zero and one can represent any graph or Boolean formula. Note that any turing machine can be translated to a turning machine over the binary language on the expense of a constant factor of the time and the place complexity using the following trick.

Let $1, 2, 3, \dots n$ be an enumeration of the elements of the alphabet. Let $m = \left\lfloor \log n \right\rfloor + 1$. Change each symbol with a word of length $m$ in the machine, where the $i$th symbol turns into $\mathrm{bin}(i)$ prefixed with zeroes to reach length $m$. The machine reads the letters in blocks (you can save what word you are reading now in the state of the machine).

Note. The way a machine encodes the input can have a big effect on its time and place complexity note the adjacency lists and adjacency matrices representations of graphs.

Source Link
Narek Bojikian
  • 4.7k
  • 1
  • 12
  • 36

The way each variable is represented is a matter of encoding of the problem and the machine does not have to assign an independent symbol for each variable. Your question is similar to, we can not represent all graphs in a turning machine since for a fixed alphabet $\Sigma$ we can set the number of vertices to $\Sigma + 1$. Well, we can represent each variable of sat, or each vertex in the graph using a binary number. Hence, a machine whose input and working alphabet is zero and one can represent any graph or Boolean formula. Note that any turning machine can be translated to a turning machine over the binary language on the expense of a constant factor of the time and the place complexity using the following trick.

Let $1, 2, 3, \dots n$ be an enumeration of the elements of the alphabet. Let $m = \left\lfloor \log n \right\rfloor + 1$. Change each symbol with a word of length $m$ in the machine, where the $i$th sybold turns into $\mathrm{bin}(i)$ prefixed with zeroes to reach length $m$. The machine reads the letters in blocks (you can save what word you are reading now in the state of the machine).