Insights Blog
-- Browse All Articles --
Physics Articles
Physics Tutorials
Physics Guides
Physics FAQ
Math Articles
Math Tutorials
Math Guides
Math FAQ
Education Articles
Education Guides
Bio/Chem Articles
Technology Guides
Computer Science Tutorials
Forums
Chemistry
Biology and Medical
Earth Sciences
Computer Science
Computing and Technology
DIY Projects
Trending
Featured Threads
Log in
Register
What's new
Search
Search
Search titles only
By:
Chemistry
Biology and Medical
Earth Sciences
Computer Science
Computing and Technology
DIY Projects
Menu
Log in
Register
Navigation
More options
Contact us
Close Menu
JavaScript is disabled. For a better experience, please enable JavaScript in your browser before proceeding.
You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an
alternative browser
.
Forums
Other Sciences
Programming and Computer Science
Is this a Turing-complete machine?
Reply to thread
Message
[QUOTE="2sin54, post: 6025814, member: 337855"] Say a Turing machine is simulated by the following rules: [LIST] [*]A number of states can be defined. [*]Each state is defined by : [LIST] [*]specifying what the head writes in the current cell in case of each symbol of the alphabet [*]specifying where the head moves (left or right) in case of each symbol of the alphabet of the current cell [*]specifying which state the current state transitions to in case of each symbol of the alphabet [/LIST] [/LIST] Is this a Turing-complete (ignoring memory limitations) machine? I have seen very different Turing machines on the Internet by some people. For example palindrome checking-capable machine which, at some point during its procedure moves the head by more than 1 cell. Or at some other point it searches for a specific value on the tape. Both of these tasks seem impossible on the approach I outlined. Does it make the approach I described result in a non-Turing-complete machine? [/QUOTE]
Insert quotes…
Post reply
Forums
Other Sciences
Programming and Computer Science
Is this a Turing-complete machine?
Back
Top