Please enable JavaScript.
Coggle requires JavaScript to display documents.
TOC Week 8, We can think of a decision problem concerning the language L…
TOC Week 8
For a program with k inputs, in primitive java, every list of inputs terminates with an output, meaning it halts.
However, in basic java, the program may hang (not terminate) if it gets stuck in a while loop, so we only compute a partial function
Basic Java Programs can be translated into Turing machines and vice versa in a way where meaning is preserved; this means basic java can compute the computable functions and is Turing complete
a function that can be computed by a primitive recursive program is said to be primitive recursive; people used to think they were the only functions an algorithm could compute but the Ackermann function proves this wrong as it terminates but can only be written in basic java not primitive
-
Semidecidability: a property, P, of natural numbers is said to be semidecidable if there's a program M that returns True if a number n satisfies P and runs forever otherwise
If both P and the negation of P are semidecidable, P is decidable. We run one step of the two programs at a time until one of them terminates - if M terminates then return True but if M' terminates then return False.
Any property P that is decidable must be semidecidable - if we run M on it, we can return True if it returns True and run forever if it returns False.
We've previously used the definition that a decision problem is said to be decidable when there is
some program that, when given an argument, says whether the answer is Yes or No. However, this is vague as we have no notion of what a program or algorithm is.
We can use a Turing Machine to solve the problem; it may seem restrictive but, in actuality, gives us all the functionality necessary for decision problems on words so fancy notions would be no more expressive.
This tells us the notion of decidability is robust as these different possible definitions are equivalent
Church’s thesis states: “any decision problem on words that can be solved by an algorithm can
be solved by a Turing machine”
The tape alphabet is Σ ∪{blank}and the set of return values is {Yes, No}. We start execution with a word w on an otherwise blank tape; the head is on the cell to the left of the word. At the end of execution, the head is where it began, the tape is blank, and the machine returns Yes if w is a good word and No if it’s a bad word
Computability: We have another version of Church's thesis for functions which states "any functions on words that can be
computed by an algorithm can be computed by a Turing machine”
For functions f : Σ∗→ Σ∗, the Turing machine must start with a word w on an otherwise blank; the head is to the left of the word. At the end of execution, the machine must stop with the word f (w) on an otherwise blank; the head is to the left of the word. When there is such a machine, we say that f is computable.
We can think of a decision problem concerning the language L as either a function over all words in L to {Yes,No} where one of these is returned dependent on whether its a "good" or "bad" word. The other option is to express it as a subset of L with only the "good" words.
-