Any format is acceptable, as long as I can read & evaluate it$.$ I will create

a submission link on Gaza Moodle for you to submit this work.

I understand that your situation can be difficult and uncertain. If you cannot

complete the work on time, please contact me$!$ We will arrange something that

works for both of us$.$

$1.(4$ marks$)$ Write, in any language of your choice, a partial recursive function. Explain what makes it partial recursive.

$2.$ How would you try to approach the Post Correspondence Problem $($PCP$)?$

$($a$)(10$ marks$)$ Outline an algorithm that you believe could be successful

in solving at least some of the PCP problems.

$($b$)(4$ marks$)$ Apply your algorithm to the following solvable problems.

Does it manage to solve them?

$$

$1$

$100$

$101$

$1$

$00$

$10$

$1$

$0$

$$

$100$

$1$

$0$

$100$

$1$

$00$

$($c$)(5$ marks$)$ Would your algorithm be able to determine that any of

the following PCP problems are unsolvable $($or probably so$)?$ If not,

can you think of any modifications that you could make so that it is

able to determine unsolvability?

$$

$111$

$11$

$100$

$011$

$0$

$100$

$$

$111$

$001$

$001$

$0$

$1$

$111$

$$

$110$

$1$

$1$

$01$

$0$

$110$

Note: Do not spend more than $2-3$ hours on this question. I am more interested in what your algorithm & answers reveal about your understanding

of the problem space and computability.

$3.(3$ marks$)$ The EBNF example at the end of the $3$rd slide$-$set is deliberately

flawed because it can be used to produce too$-$complex strings such as

$0032$ and $45\mathrm{.}00000.$ These numbers should be written as $32$ and

$45$ instead. Rewrite the EBNF grammar to fix this flaw.