{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [], "authorship_tag": "ABX9TyPwUEC6Tm/4/mEgf1LUd9Ra", "include_colab_link": true }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" } }, "cells": [ { "cell_type": "markdown", "metadata": { "id": "view-in-github", "colab_type": "text" }, "source": [ "\"Open" ] }, { "cell_type": "markdown", "source": [ "# Algorithmic problems" ], "metadata": { "id": "Plr8zrA574av" } }, { "cell_type": "markdown", "source": [ "This section is going to have a general discussion of algorithmic problems with examples from ones with a finite search space (like finding paths in a graph) to ones with a potentially infinite space (tiling, PCP and related problems, matrix mortality, and satisfiability in logical systems)." ], "metadata": { "id": "HZXHsfFfHNXG" } }, { "cell_type": "markdown", "source": [ "(content:firstTiles)=\n", "# Tiling problems\n", "\n", "\n", "A *tile* is a square with a color on each side. For example, here are eight tiles\n", "\n", "The colors involved are red, black, grey, green, yellow, \n", "cyan (light blue) and dark blue." ], "metadata": { "id": "YbfzHV7h8De5" } }, { "cell_type": "code", "source": [], "metadata": { "id": "P9Mibo1Oew1-" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [], "metadata": { "id": "_5_ALr9h_D1D" } }, { "cell_type": "markdown", "source": [ "A *tile set* is a finite set of tiles. A *pointed* tile set is a tile set that comes with a special tile $t_0$ called the *start tile*. \n", "\n", " \n", " ```{admonition} Problems\n", " :class: danger\n", "\n", "Given a tile set, is it possible to tile all of the squares in the first quadrant in such a way that tiles which share an edge must have the same color on that edge?\n", "\n", "Given a pointed tile set, is it possible to tile the first quadrant satisfying the same condition and also tile the corner of the quadrant with the start tile?\n", "``` \n", "\n", "\n", "For example, here is a tile set:\n", "\n", "The first question has a trivial answer for this set: since we have a tile with grey on all sides, we can just use it on every square of the quadrant. Of course, this is a special feature of this example. \n", "\n", "Continuing, we can turn our tile set above into a pointed tile set by selecting as $t_0$ any of the eight tiles. Let's choose the one marked in green below.\n", "\n", "Now here is a finite part of a tiling of the quadrant with this pointed tile set:\n", "\n", "We should emphasize that given a (pointed) tile set $\\TT$, there might or might not be a tiling of the quadrant with $\\TT$. \n", "The algorithmic question is to determine from $\\TT$ whether or not there is a tiling of the quadrant as requested. This means that we want to know in finite time whether or not some infinite task can be completed or not." ], "metadata": { "id": "1Dq_2wJ08VKG" } }, { "cell_type": "markdown", "source": [ "```{exercise}\n", "Let $\\TT^*$ be the pointed tile set consisting of the tiles in the bottom row of the last set:\n", "\n", "Does the quadrant have a tiling with this set?\n", "```" ], "metadata": { "id": "dFXWp0gSf6VP" } }, { "cell_type": "markdown", "source": [ "```{exercise}\n", "Construct a (finite) pointed tile set $\\TT$ with the following properties:\n", "\n", "(a) The quadrant can be tiled using $\\TT$ in exactly one way.\n", "\n", "(b) In the tiling of the quadrant, the start tile appears on the main diagonal, and nowhere else.\n", "```" ], "metadata": { "id": "JPa5mHgR_Bq5" } }, { "cell_type": "markdown", "source": [ "# Post's correspondence problem" ], "metadata": { "id": "YIAoSCgGpr_s" } }, { "cell_type": "markdown", "source": [ "\n", "An *alphabet* is just a set $A$ of symbols. \n", "\n", "Given an alphabet $A$, we define \n", "\n", "$$\\begin{array}{lcl}\n", "A^+ & = & \\set{a_1 a_2 \\cdots a_n : n \\in N, n\\geq 0, \\mbox{ and } a_i\\in A \\mbox{ for all $i$}}\\\\\n", "A^* & = & A^+ \\cup\\set{\\epsilon}\\\\\n", "\\end{array}\n", "$$\n", "\n", "So $A^+$ is the set of *non-empty* words on $A$.\n", "And $A^*$ adds in the *empty word* $\\eps$.\n", " \n", "\n", "We are given a finite set of *dominoes*, \n", "each of which has two non-empty words on it,\n", "a word *on the top* and a word *on the bottom*.\n", "\n", "For example, with $A = \\set{a,b}$, here is a finite set of dominoes:\n", "\n", "\n", "We have an unlimited supply of all of these dominoes.\n", " \n", " \n", " ```{admonition} Problem\n", " :class: danger\n", "\n", " Can we place a finite row of dominoes\n", " in such a way that the words on the top \n", " *concatenate to* the same thing as the words on the bottom?\n", " \n", " Let's call this a *Post sequence*.\n", "``` \n", "\n", "\n", " \n", " \n", "For this particular set of dominoes, the answer is *Yes*:\n", "\n", "\n", "\n", " The common word is $ababaaabbbaabbaababaa$.\n", " \n", " \n", " \n", " \n", "```{prf:theorem} Post, 1946\n", "\n", "There is no algorithm which,\n", "when given *any* finite set of dominoes with two words on each,\n", "tells *in finite time*\n", "whether or not one can find a Post sequence for the given domino set.\n", "```\n", " \n", "\n", "We are going to see a proof of this result.\n", "It is very important to understand the statement of \n", "this kind of result,\n", "since frequently people get it wrong.\n", "It does *not* say that that for each particular domino set\n", "we cannot tell if there is a Post sequence or not.\n", "\n", "\n", "\n", "It also doesn't say that there is no \"fact of the matter\" whether\n", "a given domino set has or doesn't have a Post sequence.\n", " \n", "\n", "*PCP* is the set of finite domino sets which have a Post sequence.\n", "To say *PCP is decidable* means that *there is*\n", "a\n", "computable function $f$\n", "which inputs a domino set $\\DD$ and says Yes or No as to whether \n", "$\\DD$ has a Post sequence.\n", "To say *PCP is undecidable* means that *there is no*\n", "computable function $f$ like this.\n", "\n", "\n" ], "metadata": { "id": "DnnPIGkQr7Mu" } }, { "cell_type": "markdown", "source": [ "# Matrix problems\n", "\n", "This section will present problems with $n\\times n$\n", "matrices over $\\mathbf{Z}$ such as matrix mortality. " ], "metadata": { "id": "9iFeqHSX6Gb0" } }, { "cell_type": "code", "source": [], "metadata": { "id": "mNTgdMb1H9qc" }, "execution_count": null, "outputs": [] } ] }