Skip to main content
Computer Science

Return to Question

edited tags
Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393
edited body
Source Link
micsza
micsza
  • 207
  • 1
  • 4

This is pretty fundamental but I'm getting confused. Let $U$ be the Universal Turing Machine and $L_{U}$$L_{u}$ the language it accepts which is recursively enumerable. Obviously we are not able to construct the machine for its complement i.e. for $\bar{L_{u}}$, otherwise the whole theory crashes but still let's try. Let $V$ be a Turing Machine constructed the same way as $U$ but with the final states switched i.e.: on input code $\langle M, w \rangle$ it simulates $M$ on $w$ but if $M$ accepts $w$ then $V$ rejects $\langle M, w \rangle$ and if $M$ rejects $w$ then $V$ accepts $\langle M, w \rangle$ (implicitly if $M$ loops then $V$ loops). So the language that $V$ accepts is $\bar{L_{u}}$, isn't it? There must be a flaw in this construction but where?

This is pretty fundamental but I'm getting confused. Let $U$ be the Universal Turing Machine and $L_{U}$ the language it accepts which is recursively enumerable. Obviously we are not able to construct the machine for its complement i.e. for $\bar{L_{u}}$, otherwise the whole theory crashes but still let's try. Let $V$ be a Turing Machine constructed the same way as $U$ but with the final states switched i.e.: on input code $\langle M, w \rangle$ it simulates $M$ on $w$ but if $M$ accepts $w$ then $V$ rejects $\langle M, w \rangle$ and if $M$ rejects $w$ then $V$ accepts $\langle M, w \rangle$ (implicitly if $M$ loops then $V$ loops). So the language that $V$ accepts is $\bar{L_{u}}$, isn't it? There must be a flaw in this construction but where?

This is pretty fundamental but I'm getting confused. Let $U$ be the Universal Turing Machine and $L_{u}$ the language it accepts which is recursively enumerable. Obviously we are not able to construct the machine for its complement i.e. for $\bar{L_{u}}$, otherwise the whole theory crashes but still let's try. Let $V$ be a Turing Machine constructed the same way as $U$ but with the final states switched i.e.: on input code $\langle M, w \rangle$ it simulates $M$ on $w$ but if $M$ accepts $w$ then $V$ rejects $\langle M, w \rangle$ and if $M$ rejects $w$ then $V$ accepts $\langle M, w \rangle$ (implicitly if $M$ loops then $V$ loops). So the language that $V$ accepts is $\bar{L_{u}}$, isn't it? There must be a flaw in this construction but where?

Source Link
micsza
micsza
  • 207
  • 1
  • 4

Construction of the complement of universal Turing machine - where is the catch?

This is pretty fundamental but I'm getting confused. Let $U$ be the Universal Turing Machine and $L_{U}$ the language it accepts which is recursively enumerable. Obviously we are not able to construct the machine for its complement i.e. for $\bar{L_{u}}$, otherwise the whole theory crashes but still let's try. Let $V$ be a Turing Machine constructed the same way as $U$ but with the final states switched i.e.: on input code $\langle M, w \rangle$ it simulates $M$ on $w$ but if $M$ accepts $w$ then $V$ rejects $\langle M, w \rangle$ and if $M$ rejects $w$ then $V$ accepts $\langle M, w \rangle$ (implicitly if $M$ loops then $V$ loops). So the language that $V$ accepts is $\bar{L_{u}}$, isn't it? There must be a flaw in this construction but where?