Theory of Computation Flashcards
What is a Turing Machine?
A Turing Machine can be viewed as a computer with a single fixed program
What is an algorithm?
An algorithm is a precise description of steps necessary to accomplish a certain set of tasks or solve a particular problem
or
a sequence of steps that can be followed to complete a task and that always terminates.
How do you know when a problem is computable?
If a Turing machine can exist for the computation, which halts on all inputs.
A task is computable if and only if it can be computed by a Turing machine.
can every algorithm be represented as a Turing Machine program
yes
State the Church-Turing thesis?
if an algorithm exits then there is an equivalent Turing machine for that algorithm.
What is the Halting problem?
An unsolvable problem of determining if a program will eventually stop given an input.
How is a universal Turing machines input displayed as
description number (the binary description of transition functions for a Turing machine) # input data #
hash separated
How is the description number for a universal Turing machine derived
the transition functions are abbreviated, then given values for states, shifts, all symbols.
what makes a problem intractable
no reasonable time solution (polynomial). considered unsolvable
