class forums

get help from your classmates and help yourself by learning more as you help them
 
HomeHome  ­FAQFAQ  ­SearchSearch  ­RegisterRegister  ­MemberlistMemberlist  ­UsergroupsUsergroups  ­Log inLog in  
Share | 
 

 Computation & Turing Machine

View previous topic View next topic Go down 
AuthorMessage
06b2365



Posts: 1
Join date: 2009-08-07

PostSubject: Computation & Turing Machine   Fri Aug 07, 2009 3:21 pm

A computer is a machine that performs computation on information. Computation is the processing of
information following a model expressed as algorithm, protocol etc. It is ranging from human thinking to calculations.

To study computation, several models of computation are used but the most commonly examined is the Turing
machine. Alan Turing discovers Turing machine in 1937, an imaginary machine that consists of an input/output tape. The machine could perform any computations on numbers and symbols. When a program containing a set of rules is selected and loaded, the machine would run the program and halt when there is no more rules to apply.

...........so far, so good.........

The linear nature of its memory tape, as opposed to random access memory, limits the computation speed as it
has to move its head step by step along its tape.

....oh, oh! i smell confusion here - whereas it is true that average seek times for disks is less than for tapes, this has nothing to do with what can or cannot be computed in theory.......

It is simple and powerful enough to process large inputs on its infinite work space but it can only read or write one symbol, per step.

yes; its infinite workspace (ie its tape) - how big is that, exactly? is it realistic? can we make an infinite workspace? and if not, what does that say about the usefulness of the concept of a Turing Machine as a model of computation or, equivalently, the meaningfulness of the mathematical concept of the class of partial recursive functions?

NB. the answer to my last question is non-trivial and should only be attempted if you plan on doing a PhD in pure mathematics.
Back to top Go down
View user profile
 

Computation & Turing Machine

View previous topic View next topic Back to top 
Page 1 of 1

Permissions of this forum:You cannot reply to topics in this forum
class forums :: BC :: homeworkwikis-