This website houses notes from my studies at the University of Liverpool. If you see any errors or issues, please do open an issue on this site's GitHub.
XML XML files look similar to HTML files. This is an XML document representing the graph from last lecture: <?xml version="1.0" encoding="utf-8" standalone="yes" ?> <lecturers> <lecturer> <name>J. Fearnley</name> <phone>7954…</phone> <teaches> <code>COMP105</code> <title>Progr. Paradigms</code> </teaches> <memberOf>Economics & …</memberOf> </lecturer> ... </lecturers> There are the following structures: Tags - Enclosed between <>....
Semi-structured data lies between fully structured data (like relational databases) and unstructured data (like arbitrary data files). Semi-structured data doesn’t have to fit to a schema. Programs have to know how to read & interpret the data. Semi-structured data is self describing and flexible. Semi-Structured Data Model Semi-structured data is...
We have found that: The language $A_\text{TM}$ is recursively enumerable but not recursive. Consider that we have a set of languages that are not recognisable: \[\begin{aligned} \overline{A_\text{TM}}=&\{\langle M,w\rangle:M\text{ rejects or loops on input }w\}\\ &\cup\{x:x\text{ does not describe a TM or a valid input}\} \end{aligned}\] The language $\overline{A_\text{TM}}$ is not...
A TM that decides $A_\text{TM}$ is so powerful that it will destroy itself. Proof of Turing’s Theorem by Contradiction Suppose that $A_\text{TM}$ is decidable. There exists a total TM $H$ that decides $A_\text{TM}$. It should have the following terminal states: Accept: If $M$ accepts $\langle M\rangle$ Reject If $M$ rejects...
A universal Turing machine defines a formal specification to record a program $M$: graph LR p[Program M] & i[Input x for M] --> U --> w[Whatever M does on x] The universal TM $U$ takes as input a program $M$ and a string $x$ and simulates $M$ on $x$. Turing...
Checking Decidability with a TM To check whether a DFA is decidable, we can use a Turing machine. For this we need to simulate the DFA $D$ with the input $w$ on the turing machine: If the simulation ends in an accepting state then the Turing machine accepts. Otherwise reject....
The running time of a TM $M$ is the function $t_M(n)$ where the function equals: The maximum number of steps that $M$ takes on any input of length $n$. This is basically big O notation. Efficiency & the Church-Turing Thesis Although different types of Turing machines are equally as powerful:...
Our formal model of a computer will use the following instruction set: Instruction Description load x Put the value $x$ into $R_0$. load Rk Copy the value of $R_k$ into $R_0$. store Rk Copy the value of $R_0$ into $R_k$ read Rk Copy the value at memory location $R_k$ into...
All variants of Turing machines have the same computational ability. The Church-Turing Thesis Every effectively calculable function is a computable function where: Effectively Calculable - Produced by any intuitively effective means whatsoever. Effectively Computable - Produced by a Turing-machine or equivalent mechanical device. Multitape Turing Machine A multitape Turing machine...
Test Plan Template Name of Case Description Input Data Action Expected Output Actual Output Pass LoginOKPass Tests login with a good username and password. Username=test1Password=pass1 Click login. OK Login OK True Black-Box Testing This is a method of testing where we blindly test...