Re: independence from the alphabet

On Apr 8, 4:26 pm, sanchopanch...@xxxxxx wrote:
Hello,

if one considers space complexity of turing machines, it is not
important to choose a fix alphabet, because changing the alphabet
changes the complexity only by a constant factor: You can define a
turing machine which encodes and decodes a symbol in the old alphabet
as a symbol in the new one and vice versa.

But what about time complexity? Does the change of the alphabet has an
effect on the language-class in this case?

Thank you,
S.

i dont think you understand teh limits of turing machines, especially
in view of the lak of points on a line

see my other tread on this point (no pun intended)

:-)

kisses

amy
.

Relevant Pages

  • independence from the alphabet
    ... if one considers space complexity of turing machines, ... important to choose a fix alphabet, ...
    (sci.math)
  • Re: Panu Raatikainens review of two of Chaitins books.
    ... >complexity larger than c. ... that it's going to question the _interpretation_ of the theorem ... >actually determined by the chosen coding of Turing machines, ...
    (comp.theory)
  • Pro-pro-constructive strategy for proving P = NP.
    ... complexity theory, p, np, prawns, prongs, hyper-drive ... For example, in 19XX Computers Science answered in the affirmative, ... Are nondeterministic Turing Machines inherently more efficient than ... difficult problems in polynomial time. ...
    (sci.math)
  • Re: Computational complexity (was Re: Normalisation)
    ... >> Estimating complexity on Turing machines is one thing; ... >> usable programming languages / systems is slightly different. ... Everything is reality at some level. ... But it is no better to be unaware of "practical" complexity ...
    (comp.databases.theory)
  • Re: What is complexity?
    ... >>>Since the number of Turing Machines is infinite, the sum of Kolmogorov ... >>>complexity for all programs on all Turing Machines is also infinite. ...
    (talk.origins)