My assessment repository for the Theory Of Algorithms assessment 2022.

This repository is a demonstration of my research and studies into the topics of The Bounded Post Correspondence Problem and The Countdown Numbers Game using python and different programming techniques in order to look deeper as some of the theory behind algorithms and their complexities in computing.

docker-compose - A docker compose file which can be ran in order to view and edit the notebooks using a docker image on your local machine.

requirements - The requirements for the docker image.

Dockerfile - Another file for running the notebooks on your local machine.

countdown.ipynb -

• An Overview and explanation of the Countdown Numbers Game
• Discussion of the complexity of the Countdown Numbers Game
• Python function, written in a functional programming style to solve a Countdown Numbers Game
• Explanation of the functional aspects of the code

post-correspondance.ipynb -

• Definition and explanation of the Post Correspondence Problem
• Definition and explanation of the Bounded Post Correspondence Problem
• Python function to solve the Bounded Post Correspondence Problem.
• Explanation of what an undecidable problem is in computability theory, with reference to the Post Correspondence Problem.

To run this repository on your local machine, follow these steps:

• Install Anaconda3 onto your machine. A link to the Anaconda website - Download Anaconda3
• Run this command in a new terminal conda install -c conda-forge jupyterlab
• Clone this repository
• Open a terminal in the directory of the cloned repository Open the cloned folder of this repository
• Run the notebooks locally with this command jupyter lab or run jupyter lab

Run the notebooks using google collab below.

• Post Correspondance Problem:

• Countdown Numbers Game:

• Jupyter - https://jupyter.org/
• Anaconda3 Download - https://www.anaconda.com/products/distribution