Skip to main content
Computer Science

Return to Answer

edited body
Source Link
G. Bach
G. Bach
  • 2k
  • 1
  • 17
  • 27

Maybe a more straightforward illustration of the "up to isomorphism" thing: take a TM with 1 state and no transitions, then you can generate uncountably many TMs by assigning the state some subset of $\mathbb{N}$ as its label. Since you get uncountableuncountably many labels this way, you have uncountably many, obviously isomorphic TMs.

Maybe a more straightforward illustration of the "up to isomorphism" thing: take a TM with 1 state and no transitions, then you can generate uncountably many TMs by assigning the state some subset of $\mathbb{N}$ as its label. Since you get uncountable many labels this way, you have uncountably many, obviously isomorphic TMs.

Maybe a more straightforward illustration of the "up to isomorphism" thing: take a TM with 1 state and no transitions, then you can generate uncountably many TMs by assigning the state some subset of $\mathbb{N}$ as its label. Since you get uncountably many labels this way, you have uncountably many, obviously isomorphic TMs.

Source Link
G. Bach
G. Bach
  • 2k
  • 1
  • 17
  • 27

Maybe a more straightforward illustration of the "up to isomorphism" thing: take a TM with 1 state and no transitions, then you can generate uncountably many TMs by assigning the state some subset of $\mathbb{N}$ as its label. Since you get uncountable many labels this way, you have uncountably many, obviously isomorphic TMs.