Computability

Question 1

Definition of computability

Answer 1

function if is computable if some program P computes it 
for any input x, the computation p x halts with output f x

Question 2

intensional equalilty

Answer 2

same result but different algorithmic complexity

Question 3

What does it mean for a function to be computable

Answer 3

Turing - iff can be computed on a turing machine
Godel: iff it is general recursive
Church: iff can be written as lambda notation

Question 4

Algorithm vs computable function

Answer 4

Algo - finite set of instructions which given input enables to obtain output through systematic execution o the instructions and terminates after a finite number of steps

comp - algo is used to calculate the value of a numerical function then the function is calculable
- seeks to answer a specific problem under a specfic model of computation

Question 5

What is the output of computation

Answer 5

successful result
some eror
does not terminate

cannot be solved at all - computability issue
cannot be solved efficiently - complexity issue

Question 6

Formalization of an algorithm should be:

Answer 6

Precise (unambiguous)
simple
general

Question 7

waht is the church turing hypothesis

Answer 7

prgramming language doesnt matter, all reasonal languages define the same classes of computable functions
Problem can be solved iff can be solved by a turing machine

Question 8

Turing complete

Answer 8

if can be implemented on a turing machine then it is turing complete
- i.e. all computable functions and thus programming languages

Question 9

Turing complete problem

Answer 9

any problem solved on a turing machine using finite time and resources can be solved with any programming language using finite resources

Question 10

Similar models of computation

Answer 10

register machines
lambda notation
pseudo code
turing machines

Question 11

What is the halting problem

Answer 11

given an arbitrary TM and its input tape will the machine eventually halt?
provably uncomputable, therefore cannot be solved in practice

Question 12

Desision problem

Answer 12

Problem set with YES/NO answers is called undecidable if there is no algorithm that terminates witht he corret answer or every problem in the set

Question 13

decidable problems

Answer 13

there is an algorithm that solves it

Question 14

undeciable

Answer 14

there no is algo to solve it, might be procedure but it doesnt always terminate