{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a90ef9f8022df10e",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Question 48\n",
    "Given that $A_{DFA}$ is decidable, and it will finish in a finite number of steps, we know that any DFA that accepts at least one string of finite length 3, we know that it is decidable. The algorithm is as follows:\n",
    "\n",
    "1. Start in M's start state\n",
    "2. Go through the symbols of w one at a time\n",
    "3. For all symbols of length 3, and the DFA is an accept state, we accept M DFA, otherwise reject M"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d1690ef",
   "metadata": {},
   "source": [
    "$\\pagebreak$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a7c595f",
   "metadata": {},
   "source": [
    "# Question 49\n",
    "Let us assume that $EQ_{TM}$ is decidable, then we can:\n",
    "\n",
    "1. Pass two copies of $ALL_{TM}$ into $EQ_{TM}$\n",
    "2. If $EQ_{TM}$ accepts the two copies of $ALL_{TM}$, this means that $ALL_{TM}$ is decidable, as $EQ_{TM}$ must decide on $ALL_{TM}$\n",
    "3. Therefor it is impossible for $EQ_{TM}$ to be decidable given that $ALL_{TM}$ is undecidable"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}