Skip to main content
removed reference to rice's theorem
Source Link
usul
  • 4.5k
  • 27
  • 30

This might be more comment than answer, but --

This a standard trick -- running all TMs in parallel -- but I don't know if it has a name. You can probably find it used in introductory complexity textbooks like Sipser, somewhere. One keyword is "Godel numbering", which refers to the ordering of programs that you mention (we assign each program to a natural number). I guess UTP is a fine name, you just want to distinguish it from Universal Turing Machine (UTM), which is a TM that, given the description of a program and an input, simulates that program on that input.

Your proof of undecidability is correct. But note it is immediately true from Rice's Theorem, which says that checking any property of a given program is undecidable.

Sidenote, questions like this might fit better at cs.stackexchange.com.

This might be more comment than answer, but --

This a standard trick -- running all TMs in parallel -- but I don't know if it has a name. You can probably find it used in introductory complexity textbooks like Sipser, somewhere. One keyword is "Godel numbering", which refers to the ordering of programs that you mention (we assign each program to a natural number). I guess UTP is a fine name, you just want to distinguish it from Universal Turing Machine (UTM), which is a TM that, given the description of a program and an input, simulates that program on that input.

Your proof of undecidability is correct. But note it is immediately true from Rice's Theorem, which says that checking any property of a given program is undecidable.

Sidenote, questions like this might fit better at cs.stackexchange.com.

This might be more comment than answer, but --

This a standard trick -- running all TMs in parallel -- but I don't know if it has a name. You can probably find it used in introductory complexity textbooks like Sipser, somewhere. One keyword is "Godel numbering", which refers to the ordering of programs that you mention (we assign each program to a natural number). I guess UTP is a fine name, you just want to distinguish it from Universal Turing Machine (UTM), which is a TM that, given the description of a program and an input, simulates that program on that input.

Your proof of undecidability is correct.

Sidenote, questions like this might fit better at cs.stackexchange.com.

Source Link
usul
  • 4.5k
  • 27
  • 30

This might be more comment than answer, but --

This a standard trick -- running all TMs in parallel -- but I don't know if it has a name. You can probably find it used in introductory complexity textbooks like Sipser, somewhere. One keyword is "Godel numbering", which refers to the ordering of programs that you mention (we assign each program to a natural number). I guess UTP is a fine name, you just want to distinguish it from Universal Turing Machine (UTM), which is a TM that, given the description of a program and an input, simulates that program on that input.

Your proof of undecidability is correct. But note it is immediately true from Rice's Theorem, which says that checking any property of a given program is undecidable.

Sidenote, questions like this might fit better at cs.stackexchange.com.