Does a Turing machine with inifinite states has more computable power
Hi,
The regular turing machine definition has a finite set of states.
Consider a turing machine with inifite states rest all remains same..
Does this machine have more computable power then a regular machine ?
If yes then one has to come up that with a language that a machine with infinite states can recognize but cant be recognized with a machine that has finite number of states...
or in case of no - one has to show that a machine with a finite number of states could imitate the operation of a machine with an infinite number of states...
I am currently stuck .. Cant see on a go first of all whether the answer is yes or no...and then the next step of going into proving it..
Any hints help resources would be great...
Thanks
The regular turing machine definition has a finite set of states.
Consider a turing machine with inifite states rest all remains same..
Does this machine have more computable power then a regular machine ?
If yes then one has to come up that with a language that a machine with infinite states can recognize but cant be recognized with a machine that has finite number of states...
or in case of no - one has to show that a machine with a finite number of states could imitate the operation of a machine with an infinite number of states...
I am currently stuck .. Cant see on a go first of all whether the answer is yes or no...and then the next step of going into proving it..
Any hints help resources would be great...
Thanks
David Johnson, CD
Then it is not a Turing Machine but a quantum processor.
Although I have not studied this theory, I have to ask you a simpler question.
If in one machine the number of states is N, and in another machine the number of states is 2N, then does the 2N state machine have more computable power than the 1N machine? How does the computable power of a machine with N+1 States compare to the n State machine?
What is your precise definition of computable power?
If in one machine the number of states is N, and in another machine the number of states is 2N, then does the 2N state machine have more computable power than the 1N machine? How does the computable power of a machine with N+1 States compare to the n State machine?
What is your precise definition of computable power?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
It occurs to me looking at this again, the question may have been asking about the internal states of the Turing machine - not the size of the tape (which is its external state).
If we assume an infinite tape, then a machine with finite internal states and infinite internal states would be computationally equivalent because the extra internal states for the infinite state machine could simply be stored on the tape instead of internally - making it more efficient, but not more computationally powerful. Kind of like the difference in a "real" computer between storing something in RAM or on disk. If either is infinite you have the same expressive power.
Dr. Khlan's approach to this is different (and quite possibly correct!) but reasoning about the space of computable problems for such a machine.
If we assume an infinite tape, then a machine with finite internal states and infinite internal states would be computationally equivalent because the extra internal states for the infinite state machine could simply be stored on the tape instead of internally - making it more efficient, but not more computationally powerful. Kind of like the difference in a "real" computer between storing something in RAM or on disk. If either is infinite you have the same expressive power.
Dr. Khlan's approach to this is different (and quite possibly correct!) but reasoning about the space of computable problems for such a machine.
Could you clarify the differences between
computationally powerful
more computable power
faster
Does more powerful simply mean that a more powerful machine can solve problems that a less powerful machine cannot solve? As one concrete example, a purchased IBM PC in 1980 would not have the resources in those days for a google-like company to perform its searches. Or is it something else?
more computable power
faster
phoffric - this is a question asking about the class of problems that can be solved. So speed of solution doesn't matter - just what can be done with a certain type of computer.
E.g. Some things are not computable - a famous example is "can you decide if a given program will terminate or not"? Turns out building a machine to do that is not possible. You can tell if a given program terminates (because it stops running) and you can look at simple programs and know ahead of time that they will terminate. But you can't build a machine that will take any arbitrary program and tell you if it will ever terminate. This is known as the "halting problem".
So it's a discussion of that sort of "what's computable" by different classes of computer.
E.g. Some things are not computable - a famous example is "can you decide if a given program will terminate or not"? Turns out building a machine to do that is not possible. You can tell if a given program terminates (because it stops running) and you can look at simple programs and know ahead of time that they will terminate. But you can't build a machine that will take any arbitrary program and tell you if it will ever terminate. This is known as the "halting problem".
So it's a discussion of that sort of "what's computable" by different classes of computer.
@dpearson,
thanks for the clarification.
thanks for the clarification.