L2 - Problems and Effective Procedures Flashcards
Define a Problem…
A uniform sort of questions with a defined input and output. The output must be finite and definite.
Problems are solved by providing a function or deciding membership of a set.
What are some examples of qualified questions… Explain the reason.
Given a Binary Tree, what is its height?
- Defined input and output types of binary tree and integer.
Given a natural number, is it even?
- Defined input of natural number, output if of type bool within boolean set.
What are some examples of unqualified questions?
What is the meaning of life…
- No defined input and output
Is the number 5 even?
- No uniform class of questions
What was Turings criteria for a problem being calculable?
If the solution can be calculated via a statement driven mechanical process.
Define an Effective Procedure…
A mechanism that solves a problem effectively and intuitively.
What is Copelands criteria for a procedure being effective?
Method must have the following:
- Finite and exact instruction.
- If M is error free, it was consistantly produce the correct solution.
- Can be carried out on pencil and paper.
- Executor requires no insight or ingenuity to carry procedure out.
Define a programming language in terms of Effective Procedures…Define some key languages
A Programming Language is one that encapsulates a set of procedures and problems, such that these problems can be solved by the procedures within the language.
Examples: Turing Machine Tape, Lambda Calculus, WHILE.
Define what the Turing Machine Tape is and how it works…
An infinite tape, segmented into squares. Each square can hold a value of a certain alphabet. The input is a String. A pointer moves left or right on the tape depending on whether the current statement is true or false.
How else could the Turing Machine Tape be represented?
- Transition Function
- State Transition Diagram
Could the Turing Machine be used to solve problems we see today?
Yes, but via different syntax.
Define Lambda Calculus…
System for expressing computation via abstraction and application, utilising substitution and variable bindng.
What are the 4 constants in lambda?
Integer, Character, Boolean, Operator.
Define Variables, Function and Application in Lambda Calculus?
Variable : Name that holds a value.
Function : Lambda abstraction that binds to a variable.
Application : An application of the function on some input.
X = variable, lambda = function abstraction, ( fa ) = application of function onto a.
X(fa)Lambda
Define the Turing - Church Thesis…
Any real-world computation can be translated into an equivalent computation written in both Turing Machine and Lambda-Calculus form.
