mirror of
https://github.com/saymrwulf/nvidia-AI.summerschool17-notebooks.git
synced 2026-11-19 09:50:53 +00:00
759 lines
661 KiB
Text
759 lines
661 KiB
Text
|
|
{
|
||
|
|
"metadata": {
|
||
|
|
"name": "04-linear-threshold-units"
|
||
|
|
},
|
||
|
|
"nbformat": 3,
|
||
|
|
"nbformat_minor": 0,
|
||
|
|
"worksheets": [
|
||
|
|
{
|
||
|
|
"cells": [
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Title: Linear Threshold Units\n",
|
||
|
|
"Author: Thomas M. Breuel\n",
|
||
|
|
"Institution: UniKL"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"\n",
|
||
|
|
"from pylab import *\n",
|
||
|
|
"from IPython.core.display import Image \n",
|
||
|
|
"def fig(x): return Image(filename=\"Figures/\"+x+\".png\") \n",
|
||
|
|
"from pylab import *\n",
|
||
|
|
"def figs(*args):\n",
|
||
|
|
" for i,f in enumerate(args):\n",
|
||
|
|
" subplot(1,len(args),i+1)\n",
|
||
|
|
" axis(\"off\")\n",
|
||
|
|
" fig = imshow(imread(\"Figures/\"+f+\".png\"))\n",
|
||
|
|
" \n",
|
||
|
|
"from scipy import linalg"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 267
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "heading",
|
||
|
|
"level": 1,
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"McCulloch-Pitts Neurons"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Continuous Time Models)\n",
|
||
|
|
"\n",
|
||
|
|
"In previous lectures, we looked at various more-or-less realistic neuron models that treated neurons as dynamical systems operating in continuous time:\n",
|
||
|
|
"\n",
|
||
|
|
"- inputs to the neuron were abstracted as an external input current $I_e$\n",
|
||
|
|
"- the input current was the temporal and spatial summation of individual synaptic currents\n",
|
||
|
|
"- the input current then triggered spikes in the trigger zone\n",
|
||
|
|
"- the neuron produces (under some conditions) a spike train for inputs above a threshold"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Discrete Time Abstraction)\n",
|
||
|
|
"\n",
|
||
|
|
"Assume time is discrete. Then:\n",
|
||
|
|
"\n",
|
||
|
|
"- at time $t$ each synaptic input to a neuron either has a spike or doesn't have a spike\n",
|
||
|
|
"- if it has a spike, it generates some input current that depends on the _weight_ of the synapse\n",
|
||
|
|
"- all these input currents are assumed to be summed instantaneously\n",
|
||
|
|
"- if the output is above the trigger threshold for the neuron, a spike is generated"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"# McCulloch-Pitts Neuron\n",
|
||
|
|
"figs(\"mp-concrete\",\"mp-neuron-abstract\")"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAXIAAACfCAYAAADkiVLhAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsnXe4XVWd9z+r7L1PvTW56SSBhNBB6RIIUgTFzij2sYwy\nNphRR8fyjv2VkTJYxlEZX7syioBKUZogIB0SCEII6T03ya2n7L1Xef9Y55wE55nyzDuvF8bzfZ48\neXJz7rn77HPud/3W9/f9fZfw3nu66KKLLrp4zkJO9QV00UUXXXTx/4YukXfRRRddPMfRJfIuuuii\ni+c4ukTeRRdddPEcR5fIu+iiiy6e4+gSeRdddNHFcxxdIu+iiy66eI6jS+RddNFFF89xdIm8iy66\n6OI5ji6Rd9FFF108x6Gn4oc+8NOPs/nptcyeN4RyBpPnSCmwztI3MA0hJdY58B6EQCKIIo1UCmss\nSsVYY3Deo6RCakizBs45tJBIKcGWEEmJYnU6qZMoGaOEw9s63tYQ5JA3cc4ipcQ5h/GA9zjvwDuU\nhEir8LxaYZ3DWguAaL0W50EISTvpQEiB8wapJM46hBDEUpOlKVopBILcGKzzCCkoJAnee5r1cZTS\nxFGBPHc4Z9BaIQR4PFIJrHN4wDsQQiGdQSuJ95DnOWiJkO212eM9mDRDSEGj0WBgYACXW4QQCCHw\ngHMOpSQmD/dTCPDOIaTCO4FHIKTA4/FCEK5AoKxCKkeWZezcuYf995tDnmc4Z9FaY63De4gijTEW\n5xze2869rNXqOKnIrSWKIoQAHWlWP7WBAw9eRJoZhCqgogTvYWx8AqUipBJ46SmXSpTLFeI4ptTT\nhyqUiKMIYWoIqYgPePUf90PdRRdTiCkh8ubYHkZ3jTNn3kwazSZRHOO8Z/qMWTSNQQBaSLxzKC+o\nGwNIijrBCbAuQyiBNwaHC6SmFFqqQEIInGwgcJgMoriENZqmc3gJXsRAQrk0hBSA9ygpKUqL9w7n\nDc5anHXkzQZCOZo2xVqLFhEIAUIgACUEQtAiKhASrPFYA0rFgRBNE60kNs9RrYVJKoUHrLE4Z7HS\nU2/U6dEJy1c+ztIXHB8WJ2vwWKz1CMA7j0CERUFKrHUorcAKFAIlJOBxrnWz45jx8XEGBgYwxuK9\nRUuNkOC9R0hAgNIK6T3OOWTksM6iohi8xDqDkgKhJAiBA5SWeBzlpIDc7RHKEitBljkcWXis9wgl\n8c4gpQAkqrUEFssJCEluDFJAljeJZIkockTSIoWhlGjqzT14HFWZMT42gVQxQmr27DbsyE2477qP\nGYsOZN6iBZS0RAhBF138KWFKiLynUqFvqA/lLUJGJEmJKI7JMocQnkKckKU5QsVkuSWOE6IowlqH\nEBIpFMbkCKGRUpGnOVGkyfMcISQoRSw9zufYdBybTSLjiEhoTC4pJFWUSshFjkdicGidYH0RFSmM\nyyEGBMQVj3c5UjisyVG5C1WqkOAh1gprDd4HkrTOUowFzmY4m+KtAVXEuxwRaxwapRRC+FDdCwHW\nUowlSlqkTDj4oMMZn5xES/DeIT1hwVIKHcd4FELEeOfwwuKkRMYReIEXgBDkzuCEp1gtUhveTZ+T\nREpjZA5KkluLFDJU2ELhcEgtMVlGrEtgLK61u9FaYUyGaD2/lIrUWHTk0FHEWK2JkXFYBLVCiLDQ\nWGtwEpT0GGPwQiKkotlsECcxOInJHXEUUUpKSKXxQoOMMMrS8DVEFCG8oBgVkFGBsbFRjG1inaFY\nTHBeYtOURBaoxBWw4+zdL3XRxZ8GpoTI86zJvP1m4X2DUqlMsVgCQCmFtWBNIOzwb9epsIwxSNkm\nlwgAIQQyAqkExliUCtKCtR6lAtGDxBoL0uONJ/MWIRVOSJKkjBIR0jlSMwFeAxKEwgsBWuNdW96I\nIErBgVQaEGR5FsiTUAkKr5EiAhMjXILAopwMko7P8Q6QoZoN2wGBEyC8pVRKkEIiiMBZoljhnMUL\nh8Thvcc60FEEQiKFQEiJlALhPFiHsxYvPEJKYq146slVFKIkSBxpHnYkzuOsB+VbC5IHfKighcDk\njiiKWuTriXUBQYSX4FqSTRJLvG9ijKNYKmGtb703grAjcAhceL0ifMy0DhW91hFKhvcmqsRIJVvv\nrWDu3Nl47yiVSjQaNZSKUFqSpik6VpSrZer1OnESY40lSRLqzQxwqFhiawav1B/ro9xFF88KTAmR\ne29IM0+5pKkUqmgdked5Sw4IejUInDOAQ7SIoK1D53lOHMedrwkRtHMpFErqoP86g9Yx1jrwBMJD\nkCQC54KWiwPjUgQaL2K8aGIyRZxUiJMKDoVzBoHHWYfWGiOKLXlH4p1HR/Ez6j/pwVuDlRKpE4QU\nKCfwVqNcGiQblwfuVAqtI4TTSCvwPhBlUizg80DIToqwAHmPQiKFxBO0a4THC/BCIBQgFVornHfY\nPEcIweKFi1FKYbKcpFgizVO8ABWF+6SUaunk4fojqcmyjLS1EwLITJCvEBIpaWn/EkT4/wMPXITN\nc4wxLb079AnC+6WQQqPweN8A75EiLLYOR24MsYzDTsgYenorpGmKsIJSsYKxJtxXGRbKcqkMNvQq\ndCTJmk10pHHeIPImAku4GV108aeDKSFynEBGBcqVCsJo9uwZpa+vD4HAOoNzFucCEWgdGonW2s4v\ncxzHnYYdhF/ydnPPtgjXWk8UhWozjmOMtdjcoCONcAIlY7z0eGfB5TiCpq6UxtRTssldRHER60So\nClVEJBMQMd4FOcLjcTZo1d4HsVkIDz5r6eAaj8doAaqI8jHKghQeT9DGpZDhtSUCrTXOuZZunOKs\nwRqPaHU4lU4QSpK1Gq6IoJe3G5ztpq1G47zH5gaJAjxCaYwHHSVY7zp6OwQiRwh8i2SFVBSSBGNb\njVHVanZiUFKDB2c9UVzAOUuep2gZh4obERZPFM6H57TC4VtNUO89cRw+dtYZCsXwXjbTJkkUk+c5\nxWKRPDfkuWupJL5zb6w19FZ72LlzJwBJnJBlAq1imvWMJI6wvmvG6uJPC1NTkQvJjKEh8ryJkorR\nkTEq5Qret9wSnbMuPEoJ8tzj3N4KEW/JrUUpjfMCTWg2ShlIP4oiBMHxEhSHsCDgFQIJSIQT5C5H\na0mkFXnepDnRoNpbJVKC1KdoIQhWFo21gqZRpDbtyDXeCUScoJTGe4lSGqWiIFF4h0AGZwihqpc6\nDtdsHUJYhPBIJZHK46QErRDeEicCTB1nM0SeIl2LuJFYl4fXicfmrQaod3g8Wojw3FISRVHQuFEo\nrTDOtfoKrYal91jrkFqhlAJB8KNISdTS0LUOVbu1FiUF1nkcNujpSOq1BoVi3KrqLe13TcpwL3IT\n3DdCOJwIcsu+75OQkiw3aB1RLJZwziO1J8vzIL0ohfM53rd2JEoRaY3Nc2bPmc3w8C7q9TrOxERR\nidxaEq/xtO9XF138aWBKiLzYU8bkk3ihMTYnKsR4pZAqJjMNlBJIp/HW4X2EIUdHCU5KhIDMS6K4\niMIR4bHOtn7RgzyRZWlLjpEkhULLaudAepzwSC0QeLTx4KCRGUqlCkqXMNYS7PUJmVGISAXiadlA\nClFM2syIIo3z4NMGUdKSeawnzS3Cy+DaMKGZGCUKvML5GBkVkICSOsg7gIwU1gPO463Ae4GURaSK\nkCrB5Sk2z9AStNLkxiKlRhP6Bdba0Dg1oESwOHo8QgmMtRjjUCo4e4QXKKkCOUcK4UKfwViLjqPQ\n/JSiswgJ71vyeWjuSiexxqGiVsO3tRNSLZtme6dkncHjUDq8LqVkkImcCGSuwu7K55JioRp2U8Kj\nYoX0FpOn5FkzSEUuNEvbMpCXksxZknKR1ObkWYOo2IMRExhXRUbdZmcXf1qYEiIvxGWc8wipkdJS\nrFa564GHGR2fZNGiJSzcbw4RHq0NxjRI4ggEWJujdYSWDuk1JrXEcYrwBlAt27nsVG/GtOUZjXGh\nkaekCpWlbVnqhKBYTPDeEcVA
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 268
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(McCulloch-Pitts Neuron)\n",
|
||
|
|
"\n",
|
||
|
|
"Component-wise notation:\n",
|
||
|
|
"\n",
|
||
|
|
"$$ y = \\phi(\\sum_{j=1}^m w_j x_j+x_0) $$\n",
|
||
|
|
"\n",
|
||
|
|
"Vector notation:\n",
|
||
|
|
"\n",
|
||
|
|
"$$ y = \\phi(w\\cdot x + x_0) $$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Multiple McCulloch-Pitts Neurons)\n",
|
||
|
|
"\n",
|
||
|
|
"Component-wise notation:\n",
|
||
|
|
"\n",
|
||
|
|
"$$ y_k = \\phi(\\sum_{j=1}^m w_{kj}x_j+x_0) $$\n",
|
||
|
|
"\n",
|
||
|
|
"Matrix notation:\n",
|
||
|
|
"\n",
|
||
|
|
"$$ y = \\phi(W \\cdot x + x_0) $$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Rate Coding Justification)\n",
|
||
|
|
"\n",
|
||
|
|
"The original McCulloch-Pitts justification was a discrete time model. We can also take another view:\n",
|
||
|
|
"\n",
|
||
|
|
"- each input fires at some rat\n",
|
||
|
|
"- the higher the firing rate, the higher the integrated voltage/current\n",
|
||
|
|
"- integrated voltages increase the voltage at the trigger zone\n",
|
||
|
|
"- below a some threshold, there is no spike output\n",
|
||
|
|
"- above some threshold, the neuron fires as fast as possible\n",
|
||
|
|
"- between the lower and upper thresholds, there is a smooth transition\n",
|
||
|
|
"- the relationship between input frequencies and output frequencies is non-linear"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Linear Threshold Unit)\n",
|
||
|
|
"\n",
|
||
|
|
"$\\phi(\\cdot)$ is some non-linearity.\n",
|
||
|
|
"\n",
|
||
|
|
"We commonly choose the _Heaviside function_:\n",
|
||
|
|
"\n",
|
||
|
|
"$$ H(x) = \\left\\lfloor x>0 \\right\\rfloor $$\n",
|
||
|
|
"\n",
|
||
|
|
"This gives rise to _linear threshold units_ or _linear threshold neurons_.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"def H(x): return 1.0*(x>=0.0)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 269
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Linear Threshold Units)\n",
|
||
|
|
"\n",
|
||
|
|
"$$ f(x) = \\left\\lfloor \\sum_{j=1}^N w_j x_j > \\theta \\right\\rfloor $$\n",
|
||
|
|
"$$ ~~~ = H(\\sum w_j x_j - \\theta) $$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Linear Threshold Units as Boolean Gates)\n",
|
||
|
|
"\n",
|
||
|
|
"The $x_j$ are assumed to be binary input values. What can we compute with LTUs?\n",
|
||
|
|
"\n",
|
||
|
|
"AND-gate\n",
|
||
|
|
"\n",
|
||
|
|
"$$ \\hbox{AND}(x_1,...,x_N) = \\left\\lfloor \\sum_{j=1}^N x_j \\geq N \\right\\rfloor $$\n",
|
||
|
|
"\n",
|
||
|
|
"OR-gate\n",
|
||
|
|
"\n",
|
||
|
|
"$$ \\hbox{OR}(x_1,...,x_N) = \\left\\lfloor \\sum_{j=1}^N x_j \\geq 1 \\right\\rfloor $$\n",
|
||
|
|
"\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"fig(\"gates-1\")"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAA0gAAACECAIAAAAlR5zeAAAAA3NCSVQICAjb4U/gAAAgAElEQVR4\nXu3dWaw8VdU28BecZ9HPeVaUGRFUQBAURRAZRMEBAypGEu9MjDHGS29MTNQLp+AFQVFAJgERBP4q\nk6AiH84Tzr7OiAoOOLx8P/8rX6ff7j7nf053dXV19VMXJ316qNr7qb32etaz1t613V133fVfOYJA\nEAgCQSAIBIEgEASWH4Htl78L6UEQCAJBIAgEgSAQBILAfxAIscs4CAJBIAgEgSAQBIJATxAIsevJ\njUw3gkAQCAJBIAgEgSAQYpcxEASCQBAIAkEgCASBniAQYteTG5luBIEgEASCQBAIAkEgxC5jIAgE\ngSAQBIJAEAgCPUEgxK4nNzLdCAJBIAgEgSAQBIJAiF3GQBAIAkEgCASBIBAEeoJAiF1PbmS6EQSC\nQBAIAkEgCASBELuMgSAQBIJAEAgCQSAI9ASBELue3Mh0IwgEgSAQBIJAEAgCIXYZA0EgCASBIBAE\ngkAQ6AkCIXY9uZHpRhAIAkEgCASBIBAEQuwyBoJAEAgCQSAIBIEg0BMEQux6ciPTjSAQBIJAEAgC\nQSAIhNhlDASBIBAEgkAQCAJBoCcIhNj15EamG0EgCASBIBAEgkAQCLHLGAgCQSAIBIEgEASCQE8Q\nCLHryY1MN4JAEAgCQSAIBIEgEGKXMRAEgkAQCAJBIAgEgZ4gcPee9CPdCAJBIAgEgSAQBDqGwP9s\nPe66665q1/bbb7/ddtv527Fm9qo5IXa9up3pTBAIAkEgCASBLiBQlO4Pf/jDHXfcceedd2oSSnf3\nu9/93ve+973udS8v6rjb3e6G5/lbX+hCy5e9DSF2y34H0/4gEASCQBAIAp1D4J///Odf/vKXLVu2\n3Hzzzb///e/xPOztvve97yMe8YhHPepRD33oQ//P1uP+W4/73e9+JeZ1rhtL2KAQuyW8aWlyEAgC\nQSAIBIFuI/D3v//9N7/5zY033njVVVf98Y9/lI1F7O55z3s+8IEP3GGHHR7wgAc8+MEP9uJBD3oQ\nklds7+EPf7h3SHr3uMc9dI7C1+0udrR1IXYdvTFpVhAIAkEgCASB5UUAsfvtb3/7ve9975vf/Cb1\n7j73uQ/GRrf7+c9//q9//QvPI9HhebS6hz3sYU94whP22muv3Xfffccdd/Qvtidd6wupxptiAITY\nTQFafhIEgkAQCAJBIAhsG4ES6lC6gw46CHVD7G699dZf/epX/t52221/+tOf/vrXv/7kJz/55S9/\n+d3vfhele+xjH7vHHnvsueee/voXHdz2NfKN/41AiF1GRBAIAkEgCASBIDAXBEqZQ+x22WWXF7zg\nBSQ6ZE7JHWLn+N3vfvfrX/9axpa2Z5mFFz/84Q9/9rOf/ehHP0L1dt1116c85SkD9W4u7evjSUPs\n+nhX06cgEASCQBAIAt1AQKmcmjny20477aSczmtsT3KWVofk/fjHP/7Wt7711a9+9dvf/jbpDudD\n9b72ta9ZcnHIIYccfvjhO++8szUWVW+XqruN3NIQu42glO8EgSAQBIJAEAgCjSFgrxMrZJE8Yt6j\nH/3oZzzjGWrvEDsJ2e985zs//elP6XaXXXbZLbfc4qN9th5WXfhyYy3o74lC7Pp7b9OzIBAEgkAQ\nCALdQ4Dw5pCWrcUTFsNKuVLmaHXSr/9362HVhczsf289vPjb3/7mIxV46GBWVKx/S0Ps1scnnwaB\nIBAEgkAQCALzRQBXs/sJTQ7De/rTn/6c5zzns5/97LXXXls5WdxOovaEE044+OCDn/jEJ4bYrX8z\nQuzWxyefBoEgEASCQBAIAnNEYFA/h7FJ0arGqxStPVCe+tSnfuUrX1F4h9hdcMEF1lhYgfGkJz1J\nrV7JfnNs1tKeOsRuaW9dGh4EgkAQCAJB4P8jMHgeqzeWepGBLU5sYoe6eUCF3KvXuN0PfvCDL33p\nSzY6tmHKAQccsNtuu1H4sMCl7umcBm+I3ZyAzWmDQBAIAkEgCLSHQBE7f3sgZekC0Q6rw94wPKsr\nzjnnHBV49jom2im587Ay9E7qNsRufISF2I1jkneCQBDoKAI2rDehm9kVUJvT61HiKbjp6N1Ks9pC\nAJlzWEmK+txxxx2Pe9zjHv/4x7MOj/BqqwkNX6foWhm4DfD+/e9/M/Prr7/emlmbG3/xi190PZOA\n9RaeRdYDItssfCF2E/C0uQ7n8Y9//GNY2Z7wvaneMgQNUPZGQ3YYuOKSeKapsMyPVg4BlM6GCHZD\nEMdL03gYke0PLKxjQcNHWdnIm2V3TC/mtnLjpr8dLkp355134nN2g3MoR7M/COdC5WIdyz7aGaxN\n7PTokY98pFiOu7zhhhvsgeJ5ZSYBlo7emQf0t783edM9CxYTILPQ+pprrrGJjvXVEz6e9q1yNpwQ\nY6Mtqw/lmZ785CdTmz0OednNb1pU8rsgsAkELrnkkk996lNs02+YUj1TnEGxIJO7wyxfx/3vf//h\nf73mFXgChy8sr5KxCbDy1dVAwE6/LIKa5ZkNHuSgBO3LX/6yZOXRRx9dBWo9gIH9kiGPPPJIflN3\nvv71r+uy5CwJxr9W0e6www496GZTXQixm4AkPeDiiy9mIcKgCR/P8Bb2ViodP8TBPOQhDxFU1cEC\nH/OYx9jOR91oigZmwDg/7TMCfJjqaY8bIqtXPxmUIL6eL14111RwVG9wDP7F57C9AeHzZe/4yxhx\nPo8t8sKnsb4+D6B+9U2CUmbJfm98FhHLGOZHmEPt7nvjjTf6dMcdd+yBSs3M9UJ+GW1F5rxGXm1o\nbDkF4yWUMHPm3K/bO31vQuwmYOcJJ5XCN1YcE74x21vEc6Oz/nphOFq8bdue5z73uXvvvbeKAc7G\nOI6DmQ3m/LqHCLAU0blNrdA79XZ4nr+UdXkZcz1rLaup/FSVUgxe178sDufjAuV3RP8OvtCuCs7s\nr+CKXywv0gN32MMRkC4NIWD8eySX1OT3v/99w5X72GuvvSjZW7ZskXSyCZzRLoMpXOlBRohpM3BG\neswxx7B3HfcUMqRW13bffXcqCb8Jm/hNIITYTZ4nDA7m4Sl1r3rVqyZ/Y/Pv8isVYImiPO1YJYSC\nIXqyRx1zVJdeeqlhyscoJkDyjFSOZ/MXyS+CQJ8R4Loo3GZ2BdQST5/73OdsgsCUREdMhsFK2TBe\nVI+k5+/gEOXffvvtf/7zn/kD1Uj++oKTcBUl3TkDtif0x/CIHHbPslEq2tcDj9jnAbHafZNWkpSk\nz1GtDjvsMDv3VlXPnnvuCRh1C3gPe2EaBnY/oBJ3SXZxkSI6Fs2B6j5qWytn+9HH2XsRYjcZQ7O5\nsN6KG0n9yd+Y6l1j0SHDS2/A7ZglMdnQdNRTU4iFv/jFL6xs8pc1cjCakbLQqcDOj3qIAD3bQbS7\n9dZbGYvCGuK6iAhXq8DpaU97mphez1mZsL7EvOJ53EBxO/TOi/rId3A+P2ePklkUDsEVB6n4tU5F\n8FALSw/gUSIG9HBILXOXjFueQnyC2BnJKI5/a/CLWwxpjoxwIEoZ9NIIpy+owPPpnBYI1rUYi0sw\nUkFUKRradvPNN6Nls1e4cqBCsmKxruK0DJYmIjxjp8t8S5tpe4jdZBwNSozKKCEATP7GbO9yFXUC\n3ohBkhyuvvpqT1C56qqrFEZYveHFi1/84lNOOUXVHSF9tqvl10GgbwgI0LG6PfbYY6eddjKVSzx5\n9BD17u1vf7s31VkPO49Kwg4srnxbRVa1zFbRHv1PPstf6wq/8Y1vmAE4S5GVRxgdeuihz3zmM+l5\nszukvt2G9GehCCBM4hPuw1JxkoFBW0PdC+EKIsWL8S++NmimwS/muemmm2z5e9ttt/loTuFKCees\nTDOkjLVHVRxC1kgRuZMjtTrihQ7a3E4YhsJWieFC70knLt5RYieS8PyQM844w8gTKx9yyCHkK5N1\nm5gZMXXM46LDtsT2ZF3ttWhQ
|
||
|
|
"prompt_number": 270,
|
||
|
|
"text": [
|
||
|
|
"<IPython.core.display.Image at 0xe66a9d0>"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 270
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Negation)\n",
|
||
|
|
"\n",
|
||
|
|
"To build negation, we need _negative input weights_.\n",
|
||
|
|
"\n",
|
||
|
|
"This corresponds to _inhibitory synapses_.\n",
|
||
|
|
"\n",
|
||
|
|
"NAND-gate (and NOT gate):\n",
|
||
|
|
"\n",
|
||
|
|
"$$ \\hbox{NAND}(x_1,...,x_N) = \\left\\lfloor \\sum_{j=1}^N -1 \\cdot x_j > -N \\right\\rfloor $$\n",
|
||
|
|
"\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"fig(\"gates-2\")"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAq8AAACQCAIAAACpsBWbAAAAA3NCSVQICAjb4U/gAAAgAElEQVR4\nXu3d2bMkVbXH8csgIKAgKooMMuMIDiiXqelGmtkmQLtFNJAHInzQBw19M4zwL/DJWUPFEAVUZkRB\nQabGEQFFRUBRWpBGBUEZRe7nsq91K6rq1KkhK0/WyV89nOjOysza+5s79/7ttdZee5Nnnnnmv/IJ\ngRAIgRAIgRBoMYFNW1z3VD0EQiAEQiAEQuB/CUQNpB2EQAiEQAiEQNsJRA20vQWk/iEQAiEQAiEQ\nNZA2EAIhEAIhEAJtJxA10PYWkPqHQAiEQAiEQNRA2kAIhEAIhEAItJ1A1EDbW0DqHwIhEAIhEAJR\nA2kDIRACIRACIdB2AlEDbW8BqX8IhEAIhEAIRA2kDYRACIRACIRA2wlEDbS9BaT+IRACIRACIRA1\nkDYQAiEQAiEQAm0nEDXQ9haQ+odACIRACIRA1EDaQAiEQAiEQAi0nUDUQNtbQOofAiEQAiEQAlED\naQMhEAIhEAIh0HYCUQNtbwGpfwiEQAiEQAhEDaQNhEAIhEAIhEDbCUQNtL0FpP4hEAIhEAIhEDWQ\nNhACIRACIRACbScQNdD2FpD6h0AIhEAIhEDUQNpACIRACIRACLSdQNRA21tA6h8CIRACIRACUQNp\nAyEQAiEQAiHQdgJRA21vAal/CIRACIRACEQNpA2EQAiEQAiEQNsJRA20vQWk/iEQAiEQAiEQNZA2\nEAIhEAIhEAJtJxA10PYWkPqHQAiEQAiEQNRA2kAIhEAIhEAItJ1A1EDbW0DqHwIhEAIhEAJRA2kD\nIRACIRACIdB2AlEDbW8BqX8IhEAIhEAIRA2kDYRACIRACIRA2wlEDbS9BaT+IRACIRACIRA1kDYQ\nAiEQAiEQAm0nEDXQ9haQ+odACIRACITA5kEQAiEQAiEQAktI4Jlnnhn465tsssnA4zk4CwJRA7Og\nmnuGQAiEQAiMQeDpp5/+97//XWQBEbDps5+ogTEITn1q1MDUCHODEAiBEAiBSQk89dRTjzzyyF13\n3fW3v/3tsccec5vNN998iy22eP7zn7/ttts+9z8fR57znOf4ikSISpgU9rDrogaG0cl3IRACIRAC\nMyXw+OOP33PPPRdeeOFtt932l7/8xUi/5ZZbbrPNNrvvvvsuu+yy44477rTTTi9+8Yu33377og82\n22yzHrNBxEElDyhqoBKMuUkIhEAIhMAkBBgG/vCHP/zsZz/7zW9+889//tNIb7z38d9iF3je8563\n3XbbkQJkwa677rr33nv7+5KXvMS3rAWT/GSuGUQgamAQlRwLgRAIgRCohQDbwEMPPbRhw4b777+f\nCNhtt904CMQQUAaOOyikwOyfj+CFL3zhy172sn333XevvfbaY489WA5oAgdpAhfWUtjl/CNRA8v5\n6aZuIRACIdB8AoIHDf8G9Re96EWnnHKK2b//3n333TwI9957L0HAg0AZ+Hv77bffcMMNTiMFDj74\n4EMOOcRfloOogemfctTA9Ax776AdP/HEE/SsL9iy0kx7AeX/IRACIdBHgI9g6623Fi7w+te/3j8O\nOOCAh5/9iC584IEH/vSnP3Eo+GzcuJFzgSzw1e9///tf/epXb3zjG1/xile89KUvpSfcpO/GOTAS\ngaiBkTCNdZKwWA30wQcfdBVzFlsWj9dYd8jJIRACIdA2AgZyw/kOO+xg3s/+r/pmVv/617/0qAwD\njAS//e1vf/3rX995551sBn/+85//+Mc/MhtYjEAfUAyvfvWrCQJ2gmiCyVpO1MBk3IZdpZl+4hOf\nuPnmm5m/1q1bt3r16oMOOmjYBfkuBEIgBEKgj4BwgRITwMhqWcF+++23cuXK++67j2Hglltu+dGP\nfvS73/1OsCE1IAjxTW9606pVq/ylJGIh6GO5+IGogcUZjXuGoBhy9Y477qAGLrvsMi3Vfw888EDR\nMVtttdW4d8v5IRACIdBOAmXpYFliIN8ATVDWF4gb4FAQXkAT/PznPy9mA44DJgRaQTCBRQeMBO2E\nNnGtowYmRrfghSUaVuiAf/z0pz8VK8tx8Oijjx566KE777wzf5jg2AUvzhchEAIhEAKDCBRTgcQD\nPnvuuadYAR+u2PXr1+tjGQz++te/Ci9w6Zvf/OZ99tlH3gJKItkIBrEccCzD0gAoUx5ipGIDYODi\n8WKzEk540003cWuxZZ188smvec1rLJKZ8idyeQiEQAi0mYAx/gUveIFIQ1MsHgQLDa688krdLBft\nP/7xD3OwY489llagG6IGRmwnUQMjghrvNIKUAUA6reOOO86VdABb1tVXXy0cxnoYEbCWzFpTG+fW\neFhzdgiEQAg8S8AYz3dAEIjRNvXylx9BJAELgY+ulcdWkIHQQl4DJ0cTLNpwogYWRTThCdQA59Zp\np53GNSBK9qqrrhJJ8NWvflXMC926du3al7/85QRB1h9OyDeXhUAItJ6AUd+H10Bnq0c1ATPjEqfF\nHGvFgfxF3LVyG3fSE0UTDGkym33sYx8b8nW+moCApbGXXnqp4EEBL2vWrCFOZc6yZsbYz0Lw97//\nXTOlCUhXwjbJNScgnEtCIASWDQGLsXWJTP0s/Az7RxxxhAhBk6ixKkgTkAIuJwu4aPWuJWGRfzvo\nbr6NhWA40tgGhvOZ9ltTf6EDRn3KwF/xBLfeeqsEGtdee624QkGwvAYiY0USRLROyzrXh0AItJWA\n2b9FBK985SuN+rpZUy+hhSIKb7zxRv8lDvbff3/xhulmhzSQqIEhcCr7ShNkxbLlxmGHHXb22Wfb\nrUskweWXX/6Tn/zkxBNPPOmkkzTTxL5Whjs3CoEQaCUBguBVr3qVzlYYATeBMIJf/vKXZl8We1tf\nwGyQUK0h7SJqYAicyr4qglQkgTZ6zDHHCIKlW4lW/oLrrrvOqhgGg6OOOkpkLKNWZb+aG4VACIRA\nmwjoaY33/AKve93rnnrqKf+2xEC+wh/+8Ie6Vg4IKYwYD9qEZIy6Rg2MAWvKU0sODbYsRoKSQZNc\nlUuLgJVtmy2L/4yw5VlIe50SdS4PgRBoJ4ESV8g8oHcVOvDkk09adiiukDmWW5a/oEQkxGXQ3zyi\nBvqZzPwIC4H0mVITylh81lln/fjHP5Z8W4ChVEXWGqxYsUIkwcwLkR8IgRAIgWVKQKyASRdDrChC\ncy3Z4u1xIFqLs4BpdplWetpqRQ1MS3CC66lXjVWsgMiX97znPVJk8Brcdtttv/jFLyhZMva/n/3w\ngVlQO8H9c0kIhEAItJmAPlbnaSWX7RA5YUtiIvOu1772tVZ46VqTELa/eUQN9DOp6UhRr1wGjARW\nxLJrUQNkgTzbJbmmMAJrDdi1EvlS0yPJz4RACCwXAjyzRn296Fve8pbiKZC9WKiWJd9csYna7n/O\nUQP9TGo9wn0ldYb0ROIJJCs855xzpCv47ne/SxnIVSCVYWm7tZYpPxYCIRACy4IA14BwAUGFZlmk\ngCUG9i8oUQXLon5VViJqoEqa496rRLJIQMQwwK7lr5AC4a+8BsSsJYiWG3AZaMpaMNNWIl/GJZzz\nQyAE2kygLCwUPHj33XcLHdCv2vNQ2Jb+NsHaPQ0jaqARbwpfgKUE9t3i5aJb6QCZjGmCO++8Uz5j\naw24FYjc7H/YiKeVQoRACMwJAR4BgsBaLau3vve977EQMLv6NydC1EDUQHNbcXFlHX744YJf3vCG\nN9AEwl4oWRYCf+1/SCtk/8PmPr+ULARCoHkEmFSFZ+2xxx62L7rnnnus3iIIrDhIXxo10LzW+p8S\nabUEgYYrraZIAvYAuTLoAEGFggkslfEPPjDNWpLjeA2a+yBTshAIgcYQ0FXywJpi2U3eNjFMrdQA\na4GQLKu6EqPdeVCbNuaRpSD/T4AaEAr7zne+84Mf/KDlMfQBPSul8ac//ekLLriA60uqIntzBVkI\nhEAIhMBwAtSA2CyWgAMPPNC6
|
||
|
|
"prompt_number": 271,
|
||
|
|
"text": [
|
||
|
|
"<IPython.core.display.Image at 0xe556390>"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 271
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Neural Networks as Logic Circuits)\n",
|
||
|
|
"\n",
|
||
|
|
"By setting the weights appropriately, we can create AND, OR, NAND, and NOT gates out of linear threshold units.\n",
|
||
|
|
"\n",
|
||
|
|
"Linear threshold units are one time step delay gates.\n",
|
||
|
|
"\n",
|
||
|
|
"Take together, this means we can build arbitrary computations out of these circuits."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "heading",
|
||
|
|
"level": 1,
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Computational Universality"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Computational Universality)\n",
|
||
|
|
"\n",
|
||
|
|
"- Turing completeness: a system can emulate a Turing machine\n",
|
||
|
|
"- Turing equivalence: a system can emulate and be emulated by a Turing machine\n",
|
||
|
|
"- Computational universality: roughly equivalent to Turing equivalence, but may refer to slight modifications (e.g., circuit complexity)\n",
|
||
|
|
"\n",
|
||
|
|
"Are networks of neurons Turing equivalent?\n",
|
||
|
|
"\n",
|
||
|
|
"- simple answer: \"it's logic gates, so we can build a computer\"\n",
|
||
|
|
"- but... it's sychronized in a particular way, so we have to show _something_\n",
|
||
|
|
"- it's useful to construct this explicity\n",
|
||
|
|
"\n",
|
||
|
|
"http://en.wikipedia.org/wiki/Computational_universality"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Cellular Automata)\n",
|
||
|
|
"\n",
|
||
|
|
"- cellular automata are regular grids of processors with local connections.\n",
|
||
|
|
"- updates are generally performed in parallel\n",
|
||
|
|
"- cellular automata are discrete space, discrete time, and discrete value analogs of partial differential equations"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(3-Neighborhood 1D Cellular Automata)\n",
|
||
|
|
"\n",
|
||
|
|
"- Consider an infinite 1D array $x_i$ containing values in $\\{0,1\\}$.\n",
|
||
|
|
"- The three-neighborhood of position $i$ consists of the values $x_{i-1}$, $x_i$ and $x_i+1$.\n",
|
||
|
|
"- There are 8 possible values, from $000_2$ to $111_2$.\n",
|
||
|
|
"- For each of these 8 possible values, we write down what the new value at position $i$ shall be at the next time step.\n",
|
||
|
|
"- There are 8 binary choices, so there are a total of 256 different 3-neighborhood 1D cellular automata.\n",
|
||
|
|
"- We list the 8 binary choices as a binary number and convert to decimal to get the \"rule number\"."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Rule 110)\n",
|
||
|
|
"\n",
|
||
|
|
"Rule 110 is the rule corresponding to choices $01101110$ for the 8 different outputs for inputs $111_2$ down to $000_2$.\n",
|
||
|
|
"\n",
|
||
|
|
"Rule 110 has been shown to be computationally universal by having disturbances (like particles in 1D) interact with each other.\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"# example output from Rule 110\n",
|
||
|
|
"fig(\"r110-example\")"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAQEAAAD6CAIAAAAurGXEAAAAA3NCSVQICAjb4U/gAAAgAElEQVR4\nXu1d7XZjSW5L5+T9X3lTPehFYwCSqivJtmzV/tCpy+IHCIJX8uxs8us///nP/5z/HAbemIH/fePe\nT+tvxMCvX7+6bs8OdMwc+89hYFiA1eTZgZ8z6dNJycC8AGcHStKO8ecwgAWY/+g93wM/Z96nE2OA\n3wDzV8H/HeIOAz+SAfsGGNbgfA/8SAG8e1Om+GEBFlNnB95dLj+v//1vAPR+duDnaeCtO7K/AWwf\nSmrO3wMlLcf4LRkoFb+M57fQtxznAX2VgVLo5VZY5vNb6CrVx/8VGSi1zq0o14NtnN9CrzjRg+kS\nA6XWbSuGNTg7cInt4/xyDJRaN8UPC7D6Ob+FXm6oB9A+A6XWy60Ycp4dGMg5Vy/NQKn19a8G4d8O\nwq35lP38mv91ojLmGA8DX85A9/Nm6bncjQW4k/r5e+DLp3kAXGage7svu+0GPbudWbXPb6HLAzgB\nX8tAp2bKne97enYhaOTswNcO9FS/xgCFbmGqcpx1JbpfQWcHrrF/vL+cge69rouh0ifg8z3w5bM7\nAJ7AQPdet8W4+kNoITu/hZ4wnpPioxmwF3nq/vc/EP3n/0oQrtJhQHj+udBAzrl6CQb4DVDqmxDp\nZqCXnStR9nN2oKTlGF+FAXujp9BtMXIBlmV9RQxrcHbgVYZ9cCQDqfjlo2rWBUih2/5kfljODnTM\nHPsXM1C+uXMB+GeA+dv+lNnQ4fmb+IsnfcqXDJiC4ZMLoHb+E6FlLPehLLSMZwc6Zo79yxigglP0\n+g9/9Ky63/8G+LNCuj1f1vQpfBj4LwOp4Pyhr5bh9U9S4d9J/fw9cNT3QgyUv2FyK2jpvii0peVj\naa3h81vohRTw5lBS64uQ9fLONz0suQBJoOVMh2U5O1DScoyfzQAFjUOpb/PhbnRCN/+upfO/oemY\nOfbPY+CmiAnFdJ8Qu8VYJfT7RAPP3wNJ47F8KgP6ytfCuRjd9wCjuhd/VwKB57fQp877FDMGUuhw\nSNV2+u4W4OY3BgPPDhxZfhkDnaxzMe74BkBIpspuz2+h5ORYPoMBU2fuQ6f7ZecVgM5CT39r73wP\nfMa8Tw1joBTx8qGaf/8DUfnfAzA85W6pykLdX8NwPjtw9PnZDJiOKeJyMbgM3JA8dBLvMvuedPGf\nTcyp9x4MlK9tFeFyWI900/NiiJ6Zx5Scm9ZJ/fw98B7Se40uTZcApWrGmW7roCH0VGMmWRZ6lrdG\nxvkt9BrqeAMUpstUJ5WNF7YJ3RZACSsVP3xjnB14A7m9Xov55l4YVbt51k2wBdBfNeUCMHlZ1+hp\n/wvk16PxIPquDJhM7TXP22U3z9Vw/ohPfwQy3ELUv2Tw7EBJyzE+jQF7E6/H1LpaVMFwVijMlttC\nN8uARcpU9D9/Ez9t2CdRMmBKxWNuRansVDktliGXBBbzT3iwnL+JO2aO/VEGUusr43pJl+/pdaWi\n7xYA4ZpBUWaG2f/swKMzPvEDA/YOTnWq6LttYX5bidyQeYVK/7/Ju5Ua2jtXh4GZAdN0J+Vlp/w6\nmS4HZlsHPmrsOqsPysGz81f852/ieZrn9jIDVLO9XnMxoGlVsBWbF6PbH9W97UPZzPmbuKTlGO9k\nIN/HSJRqpiWvNMQWaV0tfw1hRUZ1lq6l8zdxx8yxX2agk7WJEjq+KfSyfOpb3bpCuUgadXagpPoY\nLzNA/S3BqeZyMdKTPpuLAf9uH7qKXUvnt1DHzLFfYKAU8YpPmZae+gs+FTwsxnKGf1eI22h1tbfz\nPXBh0se1ZCD1p6plCN1SlxSo+pRfJgpgdr4ZzlTne6Ac6zHuMmDytX1YWWChm1l0H9SHbjzod4Xe\nAqjByPChn7MDAznn6gYDqXhTpy4ARKwhJlzsg+1MipsluBVlHrixHH2ypbMDycmxbDFQqkqN1F8p\nx0HcGqhQYLdAc7ZbXbyuq/P3QMfMsU8MlDKl/iB6xqtzqWP9BlhnPFp5DYQPP62QVi9xeuay3tT9\nuXt7BlTriwxTMG+X3TzprBSaP6NUmbZF5VWJSvehk/r5LfT2ir5IgL1Z8Uj98XYdzFPlyJrpz1Tm\ng0e75aPVSnumZf6zAxcl8N7upQRTf7Sof6owlZq611Rldb7dLZuuXJbWMZ6/B95b1Fe6pxwRxMfy\nl4lK0M4Zbr9SOjUvt1S8ZtNCCq/7FYTYswNXVPDGvqZLfbMOkjW5kz97MQ/ZoHuTPvVdLoCF6GKU\nAzz/7nRJyzH+iwHTXCflZe/e0wxZDsy2DnxEbIobCXVJ0mJ11cHyl3M9fw+UtBzjXwbsnc2LXAx6\n5hWilt186KlXdNaDKtvyW84VZRbdhBzt2YHk5Fj+MqAaVV4oMhpTiMajCVcD9QrnMptdIUN6WqH1\nSJ9ytOfvgZKWY/zNQMpLZYcXcylEvTIHYzb1yrorCf+Txq4uQljF8lt1PJ7vgZKWYyz+tedSdqpO\nOth7l0Is7cygelXPDIfF9M2Q4VDO9exAScu7G2ex8jW/3ErP5XBTiHCwbwwYNWeXB4HdbbmZ3VDP\nDnTMvK+d6jRFqjRNZJ0nU4HNlKyybElKHSuGzHapHEufHXhfrZedm7BMVdRlajH1pz4MVGVnkp1v\nGGQwnBqIvsyhbBbGswMDOW93lYpX7fJMt3XQkFKXMNpVmZZ0Z06GM1B/RA3JmUoz2FzPDryd0LuG\nS5V04lt2kxc9M4SeVhr2Ls+wcpon61q59Uifsvfzz0ZLWt7OaLpB/yqdPOtfpbzVPDzbH76a3AKH\n8DJb1l218iuiBMAZn++Bt5N7NmxKUo0u9axb6o/n5UOjJTR/eqpbFwtnLaeFYMdnAjC71uWVQcXj\n+feFSlreyGhyXI/QvVKgFnvL2ivW5GtJ/mju1y8c8vU8hHcjQZIukCXQV5nkfA+UtLyL0V6QeMyt\nKBVmsYsyWixDeXUpvJuHAmYV1T0Cs5YmPDvQ0fvz7aZsFW6qeVlUSakqDVfR5wLYrco05TuMARW7\nukSYUC3n+Zt4IPknX5lESn2bjwnUfhQpWUO2FYX/dP7lhuQkKP0SRoc88yzL+R4oafnhRgrI+lz2\nTj28MgdKdmkRV3TQKxTK2Dm8G0OWYJ6yqPpnzrMDyckPt3SCgH14reoVNW2yZpJ1sELmyQx60PBu\nDGUJGsu03M8y59mBkpYfa+xEZnpd/ZeSVV5Mdrxadr3C2bJBlGUGhpczyDxaF2fz0V7KnOfvgZKW\nn2lMcahorn4DlByZrHUB8GcAqpTqp1jzC8dwIpUCyNZYIp0N+fkeKEf5A42lOim7PFCIK5AKMy2W\ndqbSivSksUurSHQMXa0ZuQLWbHo+O9Ax86PsnYBUphBT6YmfLqanzlOJgw897ZBpdfEyD/21dLYw\n48y5nt9CyclPs9xUiYpGfzkM2rUfGLYPmjB1z9jMb/It1aztWN1MaL2Xoz3fAyUtP8doskhNwKJi\nUsvNX0SLKebMJAwv1Yz3uoVrEk2uI1k+jKIPA/UKt5bTpnu+B36O3LMTqgGvXnt5m3qgVw1hwjSa\n4JgKIaXmuhCtm/IdmtJa1mkizzy0nO+BgZzvfTULcfWmgltnPuLAcM2jV/aOZ0LLo0q1onikPz2t\nSgLIWrTMB5Swz7MDJS3f3jgLUYXCs/4ysQWwHy0WDrJUuF1+9bS6esXtWjlzAWz3urpkwIriUT/P\nDiQn395iCjZ5UViqbFWk9W/+9FQ3E5xWVBFrbIIsPQGyLEqjpdIVUiTWFx/PDnTMfFe7yRGPqZJl\nMc9SZ/ShP1ORoLSYOlPHVprJO0+FYXXLrwXtpYSn0z078F21XuK2eePxpuCQKrVCi2VIhVG7mgrq\nXLEdDHPuPOmmCPVMKmi0g8Ez6s4/Fyq19C2NGLz9EliP+qZUn1lS9LQMuQBqKc/IkDAyVXpiEl1r\nOqfUPZFrpznaswPJybe0mAJK
|
||
|
|
"prompt_number": 272,
|
||
|
|
"text": [
|
||
|
|
"<IPython.core.display.Image at 0xed21d10>"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 272
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"# interacting \"particles\" in Rule 110\n",
|
||
|
|
"fig(\"r110-interactions\")"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAkEAAAGgCAIAAAAiliRAAAAAA3NCSVQICAjb4U/gAAAgAElEQVR4\nXu2b4a70yGpFM1He/5VvJkJpIW+zD2W33VX2uj+u+mCKggXY8Enzz3/+85//4n8QgAAEIACBBQn8\n94I+4zIEIAABCEDg/wjwDaMOIAABCEBgVQJ8w1bNHH5DAAIQgADfMGoAAhCAAARWJcA3bNXM4TcE\nIAABCPANowYgAAEIQGBVAnzDVs0cfkMAAhCAwP+MIvjnn38+R+K/LcsStab//VnoZ3nHZr5r9Gz2\n6lv+YDMInOFZnc2WO9WSc9HRv7NitSM61X5FddFB89TGaH5Dv1O3v6qu0Yj6fupbYtNT7GH6kkEC\nAQhAAAJrEBjYw3QK0G9pDtrrh6bXyZOj11Rr+vUetYDNq/N7vlrOWLinQvoeXudP5HG0/q/zp89E\ne1Alz/azH6/P77qUcrXs/mYP28WCEAIQgAAEFiDQ2sOunserGUHv1YmyOpvZ+wklNPWuMxaw2efZ\n0VSdLPH5/VWFVN1/pz8VN5VT7dqzxyTfym91e5Upvbey4PtFT6nlUQtnbOrtmcC/v9nDNkD4EwIQ\ngAAEliHQ2sPiS3jntzf45Xt1crzfn/DK36tTg9d/s00lk/umyniWq05locNZdc5kU8/qW0EJeIna\n7OiHjrLyZ5WGSkb9UQsqwWYnX5q7+6tLc6eSb2VTo/tI2MMMHB5BAAIQgMDUBFp7mH7zveRb395q\ncvS3B289m/MwagGb3+XpK8Rnx5/VTHUkV9j0ff+rGONef7sSu4IPNvWNpF2m+ap01FolWZf8bk+x\nh+1iQQgBCEAAAgsQaO1hOQ6dAqqnIf/WxKf36oSy7nwxSknZrhK79kSOXbN8T3WduaVDvrLfOTta\nG5VNZUsHKZMqU9pxHUmVi+qW0O/nxdfG6O1XRPQtm5nY5jd7mIHDIwhAAAIQmJpAaw+b4XvuJxQ/\nj0QGvM4MMT7bT42umoJ9ptSOSubJZu7+7NX9MdJBkYt5asPXQM5XriLtmpCoteqU9otK5qGUo9j9\nzR62iwUhBCAAAQgsQKC1h+U49GvvJdd9z6vp41f+nKEUZ3XCeoZNjU5zpDodyXXVdZ58tnDG2nUx\n0kFah15yXS60Qrwn2h3Zt3zW27kzIo2xI1EPN53FHla9apBDAAIQgMDsBAb2sHm+59mT+ErrRKlf\nb+9/JMrrYDOXs2dVaVYMvbXqVHXLPNnse3hnjHTQ/PV27M2W49Is96txzg7K/n9+s4ftYkEIAQhA\nAAILEGjtYbN9z/2E4iesyInXuXMizjXivVLPZ/ZTvdVu8HVVWViFksYbkhmyRgfNk4tOned85brq\nbF2j/aL+/LZi9fZNZ7GHVa8a5BCAAAQgMDuB1h7WmQIiUP/N1y+q1+/bDDuj1q7zJ6d91CuNei0/\nNRdaP8pEG0V1vGQ2SurPzDFq1rQOVaIx+hypBZVgU98enmomljX9qbXIa+98JOxhBg6PIAABCEBg\nagKtPWzm73n2Lc/7Ks95GI0ozmIzOFSTsvIJSZZXOv3sVLf3LdyTTd/3vgLvjLHKiMrPEL6H+Z3c\nztAY9bN6s1U+zFNdlYdaDypRSrs9xR62iwUhBCAAAQgsQKC1h+U4ZpvOqgklyyv/Q/7UmcXHdUXs\nPheaBe+hTmFe/4qIvmVTYw/JDDH6rK3LfNTzGXIxWm8Ro38nV7XXuUt1fkUpR7H5zR5m4PAIAhCA\nAASmJtDaw3717T02SelsEhnw1taKMdeUj+u3sXvfqg1AO8bb0RjnyWaOJXs1GtGdMdJBo9m5v96y\nh7mPtHe0cjqS+yOqvKoi+sjZw/5EhAIEIAABCExKoLWHZd9nnlCq2UTlZyKKs9gMDtW8dqZO8llv\np7r9TH6/ZbPqeB/Rb6tLqzokKj9D+LcxnvH8W7VxhmenfvoxzhCR1kOWqIebzmIP2wDhTwhAAAIQ\nWIbAwB7mv//6tfT6QcjrjNoM/Wpy9Hdd4c+bbfpc5P7Ieal+j1bCPOSrSNXDGWL0WaOD+tm8Ir9a\nIX1/9Owq2cwx7v5mD9vFghACEIAABBYg0NrD8hd7re+57mSREz+DrBVjrjIf129j975VNeZP/TYi\nT77q/rWqiw4arcAr8lvVUqf+9ewMEfUpqeYmIvYwTTESCEAAAhBYg0BrD4sv4ejXOwBU87U+PSbR\nr7ROjtn/X/mTy2GUZBXjKjZ9vDm6rOlPabXMRkn90VfCzDFqp1SddaYO589jFZ3mdzSbndhVp/JH\nNfW97T28JyLvg0aR4939zR62iwUhBCAAAQgsQKC1h41+OWf4nucZpJooc35WjDH8957PnIuK//wR\ndcj77p8/RjooMvirDqpqTOWVh7nG9B1YdZ/a70gqH87cojZ3e4o9bBcLQghAAAIQWIBAaw/Lcaz7\nPQ/P/fwbka4bY5Upjasj0TlolJ7ekm1qRvTGtSLSeLP/+lTj/S5hvfGYJPzUfHWsrRXjDPVWUfVy\nffok8jkvm9/sYQYOjyAAAQhAYGoCrT1s9e+57lU6Ua4eY66y0Vn+/tirjFS9Mn9E4bn6mSPKnFVz\nVHJn1qp8qfxMHSrDO2M84/m3/KwIBGelnSVaPzNEpD6PepX1d3+zh+1iQQgBCEAAAgsQaO1hOQ79\n2nvJtyaUM9/z8KEzy0SkPiLVmSFG9UolM/jZYduvtxkiUs6+7zsEzlR75c8Zm3RQUL2u3vTtpHms\nsqCZzRJfb9dF1O9ijTRL1MNNf7GH+RcOTyEAAQhAYF4CA3vY6t/zSEI1y8TTJ8WYi87HdU/sfp7y\nHupZr39PRHqL+tnPgp6dOcbwbdTDtWLs504rQSVV7Jmh6mQ7XlMz0tE/E6N6O1oPHUrZw93f7GG7\nWBBCAAIQgMACBFp72DO+5zqnxBxRyXP2rpgv3mPT90GHw5lc3DMtahRV1L/yRz30ksrPfIoOiiwr\nk37FZoZaM2r5WNb6/pyPSC2opKou9VM1N5TYw7RskEAAAhCAwBoEWntYNSn4iSAA6ByRwYxaOG/T\nT473+6MRqUQnkVX81Fj62deq81HPRkn90VeCj0jpqc1RC+dt0kHB8Ipc9LtD8/iM6urEtYmUPUxT\njwQCEIAABNYg0NrDRme9KyaU62xGdM+OMRfjaKRxNp/q5EJPVT5U1vKNo7ePxlj5UPlcRaf3Vq8B\n1Vwxxmon6/C5gvkzbHYqQXWqftFcrEtpt5vYw3axIIQABCAAgQUItPawHId+/6unIffzpurcOSNo\nLCFR+boxnvH8WC40p96H6umx2329/crmU2PUTqGDlEmVfe0Urd7qbLUBn7ld/VHJDB2Umfz7mz1s\nA4Q/IQABCEBgGQKtPexX316dSrxk1M9qlsnynEl/e2g+dQ7qxF4RiLNKJkvU/jPI5yhyfWq8o5LR\natfsqGTUJh0UDEe5jZL3tXH+9lF/VL8jOeZn7qDd3+xhu1gQQgACEIDAAgRae1iOw08EoakT9xkL\nd9oMz58d4xW56HCrZnatlizxuTg22d1js+p+f/ud1f6rSlg9xu9y0zqp6n/matcu/hYljXpDjD1M\nSwgJBCAAAQisQWBgD/Pzo34tvX7g8Tp32tQ5IiQqz4n1/s8W4xnPq1x4PpmA11TaHf0rIvquzb61\ninDfgtbbnTY1X5rTO/2Zn5vmSxmqzjHJuuRzHnd/s4ftYkEIAQhAAAILEGjtYdV0EPHlp8ckM8wI\n4UM1OT4jxk52RnORuWm9a+V4kqO3XxHRt2wqjZA8KcYqv5U8M/GVoFl4EjeNTmmoTkfyJErBRCPa\ndBZ7WPWqQQ4BCEAAArMTaO1h1ayts4OX6BfV6wc8r3OdzbjX364eXudPLqVRr+7x87yHZyzMRl79\n0ZfBaB7V5qiFeyohvzFGPVwrxtGK7fP33J5NSWPX3vlI2MMMHB5BAAIQgMDUBFp7mH4VvWT1GSFH\nV02Uq8eYq9JnMzSVSWWho6k6
|
||
|
|
"prompt_number": 273,
|
||
|
|
"text": [
|
||
|
|
"<IPython.core.display.Image at 0xeb56d90>"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 273
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Tag Systems for Turing Equivalence)\n",
|
||
|
|
"\n",
|
||
|
|
"- consider a FIFO or a string\n",
|
||
|
|
"- a tag system consists of rules that match and delete at the beginning of the string and conditionally append to the end of the string\n",
|
||
|
|
"- tag systems are computationally universal\n",
|
||
|
|
"- Rule 110 can be transformed into a tag system\n",
|
||
|
|
"- therefore, showing that neural networks can implement Rule 110 shows that they are Turing equivalent\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Tag Systems and Rule 110 Example)\n",
|
||
|
|
"\n",
|
||
|
|
"http://uncomp.uwe.ac.uk/genaro/rule110/ctsRule110.html\n",
|
||
|
|
"\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"fig(\"rule110-construction\")"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAuYAAAGACAIAAABuvjDeAAAAA3NCSVQICAjb4U/gAAAgAElEQVR4\nXuydB7wURfL4Z/dtevkRRBRQEJSggoCgBBMKembvVDBnRcx6Z05nOBMiYs6CqJgwK0YEBREBA4oJ\nESTHlzbH/7e6duct8PDgfAj8fzOfx9Db09NdXV1dVV1dXePKZDKWczkYcDDgYMDBgIMBBwMOBjZv\nDLgAz9FaNu8xcqBzMOBgwMGAgwEHAw4GLJejrzhU4GDAwYCDAQcDDgYcDGz+GHBv/iA6EDoYcDDg\nYMDBgIMBBwMOBhyVxaEBBwMOBhwMOBhwMOBgYAvAgKOybAGD5IDoYMDBgIMBBwMOBhwMOCqLQwMO\nBhwMOBhwMOBgwMHAFoABR2XZAgbJAdHBgIMBBwMOBhwMOBhwVBaHBhwMOBhwMOBgwMGAg4EtAAOO\nyrIFDJIDooMBBwMOBhwMOBhwMOCoLA4NOBhwMOBgwMGAgwEHA1sABhyVZQsYJAdEBwMOBhwMOBhw\nMOBgwFFZHBpwMOBgwMGAgwEHAw4GtgAMOCrLFjBIDogOBhwMOBhwMOBgwMGAo7I4NPBXYyCZTMbj\ncW01lUqRIEd/5n/xSh9VV1fro3A4rAktTEkuLUNCK0wkEpTRSuyqeKSvaJl0Ok2ZSCTSsN1etWpV\nfrU2tNqKDZjdUztBAdLaEYUtFovpWwqwjauGBXiN2hQevSu0FLATNkjBYJB8xa1Cy12BJ18Tilt7\ndBT+UCi0dov2i/ZgaYuab9OGDcZGxYBWboOk3bRpRjurmflArgukqqoqHlFSsaGI1cqVVHiqOOFR\nfuV2Or/XpDUfRGm+JtYYl3UBY+crAPZ80Xx+6iDylIuf9nDYL1LAhtNulEwb2mg0qoVtytd5Z+fr\nU8WnYoM0fcnvJmX0kQKgqFPYbFDXaIWfikZqU+K0Ya43kQ+zgqotakfoPgla16p4VC/8FNBG7ae1\ntbU0ZxOPjcB8PvAHcFJeka+tU9UaNdhzSjulQ6Bl7EaB1k5rd7Rra2BMx0Wh1UbphaJF39Jq9V3u\ndiv2XNAh05/1InmjZjoqy0ZFr1P5ahhghjBvPR6P1+vVSajUT46Wc7lczARlUgUFBWSWl5fDDpii\nRUVFyuAorDOTwlwU5k6FFNY7P1euXDl37lxVd3w+H6/Qrr5FJUzCwsJCmyn8+UEChsaNG1NPIBBQ\nLga0dASGpXyKvtAugAGJFiBBp2xOpJ11u91k+v1+KiQBhCSA/89D+Mc1KOeiRaAC28BJeYQu+FRe\nRr6ysOLiYh4pIwZaEty5tFP0gkrALX2nTn6SAH66yYtggPLkIw+++eYbu87KykpapCS4okXtuA0w\nxXSkGnC81oUNOqutKOUAlQKvfVSGrsQGcnTI6q2KDlZUVKCa0B1IgjLaWX0FUgHJYAyc0BCPqB/k\nKCWDn5qaGq12xYoV9kDQLq9w19EBTiqHVFS4lpSUqBirFx4dHQooANRAW7QIhNTDBQA8sp9SCZk6\n9NprCiicPLIJkmElX1u0M0loc/qKdp/BpUJIKB9ppOkCF0/BJ/BQQBEFhJSHkLRTlAQMnUrgB+wx\nv2iX8hRQmqRdkMDEV5ZSLx7AlQ6lilvaopjeeUv5AwVonaogSx7VCz8FdOx4ChKArbS0lMSGwqnI\nBwYqVPxr60wTcpQM6CmAaad0DtIc4w7lKMC8aLMU0nQNnFAPCeCnkuXLl9MX6qE5HT77RW0U1Cla\nuINkmtZ3FTDuOpd1iClDPcBjj3i9qN6ImYo15+5g4C/AgOrsP/3002WXXbbffvs98MAD2uibb74J\niSt3IMHsatq0Kdzn4osvvuqqq7QMP0kwG3UC29AqN9RH3D/55JPOnTu3bNly6623ZsbefffdzH8t\nfN111/Xu3Zs7AMBfGrC/gERtTGOtE55CAj7CXRuCv2gBOIKWWbZsmSYQS5qga7BU0vq6ZnLXTPvn\nxkjouFCzwgybO/vss7/77jtyQO8LL7ygUkHZEGyuUaNGDMd//vOfW265xYYfOBVU+qg419oUYEXR\nDz/80LVr1+bNm++www7UdttttyGrKMAr1157LSQxdOjQGTNm6CtUouoLCNHXN0bf16gTcUjOt99+\ne/DBBx9xxBH33nuvNg0MAPPzzz/TfaiXMgrbukDiLS4dbnAIlsCq6iX2KwgScqjHHnGbVu3KlexV\nLvKiPVKLFi3iJzVrTj6q1wbJfotHdFCpMb8YACgkZOZXRf4a1KjTzR4ayp977rnTpk3T2hg+VSYg\nGKT+/vvv/8svv/CIWXzDDTdoVfaEVeSQWVZWhvxDDDNhe/ToMXr0aHClYCjkNsBvvPEGhW1xyFu6\n9lDdJb+bayNBc6A3KidNnWPHjj3jjDOOPPLIt99+W58OGzYMMKgfSJo0afIH8OsA6ejw7v8Mp9JJ\nPrTKRubMmXP88cczWAptz549VScDtu233/5f//qXAgBWr7jiCu0ORKJgaA2kx40bd+KJJ2677ba8\nCz2/8847ixcvtgcUDNhj8fjjjytW27VrR4Ly0LlNrtQMnLSowNCc/eK68Lzx8h0ri03/TmKjY4Bp\nAKv9xz/+wWy5/PLL77nnnuuvvx7ehF6/6667shqA0JcuXYqBhGKwPEwsPOVi6rI2VdVeV282rKr1\n85N3mZCnn346cxjRsmTJks8+++yhhx6CAzLlTjnlFBjTP//5z1atWiE1Ea7MwIbqsK5p6AVsgjph\nCiTgfY888sjNN99M68pngVBtRZTZaqutYNkwUDjjiBEjqGHy5MmqtPE6BeAR3E8++WR60VBw/nE9\nCjx87dJLL3300UdZgiOZVEFBBbRVE5DMSLE45g78DBPVMkBIKS6YGh1HkCgGVN5TgLFbsGDBbrvt\nxuj8/vvv33///bx58+64445XXnmFp8cdd9ynn36K1oImN2DAgN9++41M+CYoJaEI+WPgG+QpQNKd\n2bNn77777oABib766qv33XefwgA8r732WocOHZ544gkFb12NgjcGFOB5ZeLEiQhFJPGOO+6ITvbB\nBx/wFhwf8sMSg2ikDDk63LriV/FAJvU89dRTzBewragAz5q/zTbbkOjSpcsXX3yhaiX3dcHD3OF1\nvZhTyLyXXnpJu6CZQMuQNWvW7LnnnmP4AEBxrk8pCemSA8xAQprBBewXX3xxyJAhjz32mGpdFINa\nwBsFGMdff/0VykeJoTAVqkDVnpIDqtUSSRPQzNSpU3kFGoMkkLJKRbxFhUx/nT5ggynTokULTYAK\nKHD+/Pk0RzHgUQzQ0LrwwIt0H4sIBdBKAR4E7rHHHqeeeuqkSZPIhC8xRlQIeKjX64KfAjTHU7Wt\nqo7O6/8DnHRfcatIpgv09+GHHwa2jz76CGoEWnpK5vPPP08C1I0aNQq2xtqMV2gaLHHRNNwDsLXv\nIBCcnHnmmWhdCxcuhJ32799/0KBBrBZokdpsaClJum3bthA2kEBOYBUmrEYmCvOUmqEQugx9ahNU\n/gf0pjBspLujsmwkxDrV1o+BCRMmwKlhc3vvvfezzz774IMPQv0oEGq3ZELCN5F8cEZlCrAYJgzz\nFsbNpOItuJtWrSKW1zXBdBo+fDiCYeDAgfBfpjfMiFUyOgE/x4wZAws46qijzjrrrG7duvFTxUP9\nUG54rvJNJjacHQ5C5V9//fW///1vFqBq+qZKTfBImRSFQQX5MKNddtkFjYq+8JPuaG0wpmeeeQYO\nsuHgbNgbQILUATCAR5nAxAVg9IJBUfWLNGgEpSRQtmBbjAiyDXMLdyQByz50Qdgiq2p6oasxgCDN\nU96iGINOgWOPPZbe8Wi77bZDcML06S+CnDSDi8RCeWWIaYt3wRgldUm3YV36n0rTHHiYMmUKmuJF\nF12ETQ6Cefnll8kEGMQDI4WeDeToLn/QAnjjFdg9KD3wwANRyFg0f/nll6eddho/0fOgbV3Ngxnq\noaQOPZhBapIGvaQpo6YIfUph
|
||
|
|
"prompt_number": 285,
|
||
|
|
"text": [
|
||
|
|
"<IPython.core.display.Image at 0xfd2ced0>"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 285
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"# Rule 110 Zoom\n",
|
||
|
|
"# http://uncomp.uwe.ac.uk/genaro/rule110/ctsRule110.html\n",
|
||
|
|
"figs(\"rule110-zoom\")"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAXMAAAD4CAYAAAAeugY9AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsvHdUVFfb/73PmcbQmxRFFEQRlCo2QEERA4waQUGiKNiN\nXWNMNCaWaIyaxBKN2BIFW6JoYqJij8SS2GKKJUYTTVHBAhgLZWY+7x95Zi/0uZ/f737Xu96V9dyL\n71ou58xwrr2vuq997escBUDUox71qEc9/ldD/acnUI961KMe9fj/jvpgXo961KMe/wGoD+b1qEc9\n6vEfgPpgXo961KMe/wGoD+b1qEc96vEfgPpgXo961KMe/wGoD+b1qEc96vEfgPpgXo961KMe/wGo\nD+b1qEc96vEfgPpgXo961KMe/wGoD+b1qEc96vEfgPpgXo961KMe/wHQ/lMDW61WIYQQgNBoNMJs\nNguNRiMURRGAUBRFWCwWoSiKUBRF3gfI31VVFVarVVitVqHVauXviqIIq9Uq/9doNML2PjGLxSI0\nGs1Tn21j2v6p6t9rnO3+ut/9K9jus41lmzPw1Hj/t3kBQqvVCkVRRG1trdBqtZKfumOpqirqvh/N\nRstsNgutVvvUGKqqyrk8e22bk+2z7T4bfdvYz/Ji050QQtKzWCxSRrbf68677jg2XdflX1EUYTab\nn+Kx7lyelUddnuvq0DZ+XXv4P8nJZkN15/qvZG0bsy7fz8rZxkddWdT97l/JwzY/m1xtc68rFxu9\nurz8Tzqy8Wibk01vNnnabM02Zl0br+tXNn3YbLeuH9S1yWd5ssnkWbutq4O649TU1AidTveUPGzz\ntc3jWXutqqoSGo1G6riuDdTVW13f+1e2YKNX199s99niUt2xn+XhWfuzyfZZu342JtWFqqqitrZW\n6qyuzdcd+/8UfySt/+tf/P8EmxBtE65rnDbYPj8rjGcZs91bd4GoS99sNkvadQOrjWZdJ3128bDR\n/594qDvev1K+zemfVW7dBcDGk80469J+NojU/f5Zh6prEHVlavvOZmQ2Y32WdxufdQ3IYrH8H2VU\nNwg8a6y24Fz3nrqB2oZnF0KNRvPf5mLj7dkFsC4t2z02mf87cqqrm7r/PxvAn11gbPfXtUebnP5V\nAPhXNlHXRuv+VtcP6trKsz5Tl9azOnpWdnVhC5TP6sb2d8/Sriu/ugnWv5JtXXt7VpbPjq8oigzk\ndWk9G8jr8gcIvV4vdDrdUz71P83JYrFI/3+W37qB05ZE2X6vu4jVRV1ZAUKn0z0VfOve968WvLqJ\nYV1Z2WzZ5gN1F+9/J5AL8Q+XWRRFEXFxcWLIkCEiJCREeHl5CUdHR1FaWio+++wzMXz4cNGwYUNR\nWloqAHHv3j3h7OwsSktLhaIoYvbs2UKj0YiysjKxePFiodfrhUajEYsXLxYODg7C3d1duLi4CEdH\nR7FixQoxaNAgodVqxYIFC0SvXr1Ew4YNhbu7uygrKxOXL18WCxYsEI0aNRK3b98WQghx584dYW9v\nL27duiUsFovIzs4WWq1WlJaWihEjRgiDwSAMBoMYO3asaNOmjfD29haurq7CYDCI/fv3i9mzZ4u2\nbdsKLy8vUVpaKsxmszhw4IDw8vISZWVlQlEUsW/fPqGqqigtLRXHjx8XTZs2FaqqipKSEhERESGc\nnZ2Fj4+POHPmjHB0dBQ6nU58/PHHYsKECaJJkyaS9sOHD8XWrVulvFRVFadPnxZ6vV6UlpaKy5cv\nizZt2gi9Xi9++OEH0bVrV+Hq6iq0Wq1ISUkRGRkZomHDhsLDw0M4ODiIn376SRQUFIi+ffsKHx8f\nUVZWJjQajbhy5Ypwc3OTOlm+fLmcf0FBgdDr9UKv14v169eLBg0aCHd3d2Fvby88PDzEW2+9JXr1\n6iV8fX2Fi4uLuH37trh48aIYN26cOH36tDhx4oSYNm2a5EGIv53CZhNarVaMHj1a6HQ6ce/ePfH6\n668Lo9EoVFUVr7zyiggICBBeXl7CyclJ6HQ6sW3bNjFp0iQRGBgovL29RWlpqXjy5InYtm3bU2Oc\nPHlSGAwGUVpaKpKTk8VPP/0kSktLhbe3t+jSpYtQVVX8/PPPwmQyCUdHR6EoiujTp48wmUzi8ePH\n4r333hN2dnbC399fzJkzR6SkpAhfX1/h6uoqSktLxXfffSfmzp0rfH19xe3btwUgqqurhYODg7SD\n3Nxcacvjxo2TfE2YMEGEh4cLb29vKfczZ84IFxcXUVpaKo4cOSImTpwoGjZsKMrKyoSqquLJkyfS\nT/z8/MSqVauEj4+PCA4OFjqdTpw8eVLY2dkJIYQwGAzixIkTwsPDQ87tk08+EYqiiNLSUrFv3z7R\noEEDodfrxe7du0WrVq2kjYeEhIiJEyeK69evC19fX/H+++8LnU4nGjRoIG2htLRUfPrpp8JoNAqd\nTid27twpZWPT68yZM4VOpxOHDh0S8+bNE23bthUNGjSQ+lEURej1emEwGMTOnTvFn3/+KYQQYsyY\nMUKj0Yi7d++KadOmCYPBIFRVFdOnTxdBQUHCy8tLLF++XERGRornnntOODs7i9u3b4vdu3eL4cOH\ni9raWrFkyRJRVFQkfH19haIo4sSJE0Kv14vbt2+LS5cuiZiYGKHVasX58+dFYmKicHZ2lgHcllxo\nNBoxfPhw4ePjI9zd3UXfvn2Fv7+/cHFxEWazWVy7dk3GGUVRhJOTk9BoNCIlJUVoNBrx559/ipyc\nHOHg4CAURRH9+vUTXbt2Fb6+vkII8d8Sg/8R/EMwm81YrVYSExMBKC8vp3379nTp0oWamhpeeOEF\nhBAkJCQwYsQIoqKi0Ol0NG7cGBcXFwoKCsjLy6Nx48bExMRw5coVjh8/zjvvvEOXLl0wm83cvn2b\nmTNn0qVLF6xWK3v27MHFxYUWLVpw7NgxvL29SUxM5PvvvycsLAytVkuHDh3o1KkTGRkZODs74+Hh\ngY+PD4cPH2bmzJl07tyZTp068eeff3Lu3DmKiopITEzEarXy6NEj8vLyJE/vvPMOQggSExNZvXo1\nRqMRRVFo1aoVqqoyY8YM2rdvj16vp3nz5pw7d46tW7cyYsQIunbtyl9//cW1a9dISkoiOjqaK1eu\n0KVLFwA+/PBDFEWha9eu7Ny5E3t7exRFITIykoYNGzJ27FjCw8Oxt7cnICCAb775hjVr1pCdnU23\nbt0oLy/n4sWL7NmzR863pqaGbt26kZiYiNlsZsSIEaiqSmJiIi+//DItWrRAURQCAgIwGo188MEH\n9O3bF1dXVyIjI7l06RKHDx9mzpw5ksYff/zBO++8Q2JiIhaLhZMnT9KoUSMSExO5cOECkZGRqKpK\nbGwsCQkJqKpKfHw8JpOJ5ORktFot3t7eeHl5sWfPHiZNmkRERASxsbHcuHGD06dPU1BQIHVQUVHB\nuHHjJE9r1qyRctq+fTt2dnZSTt7e3kycOJFWrVohhGDYsGFoNBrWrVtH06ZNOXHiBO+//z4ZGRkk\nJiZy9+5dLl68yOHDh6VNWa1W/vjjDxYvXizHPHPmDP7+/nTp0oXLly/Trl07hBB07NiRpKQkTCYT\njo6OeHp64uPjw8GDB5k+fTrt27cnPj6e33//nXPnzrFp0yZpyxUVFQwbNozExERcXV3p2rUr9+7d\n47nnnkOj0ZCQkEBmZiadO3dGVVV8fHxo27YtRqORsWPHEhMTw8aNGxk8eDAJCQlUVlZKW1IUheDg\nYDQaDW+99RbdunVDURRCQ0P5/vvv+fTTT5k4cSKJiYk8fvyYX375hXXr1kmdxsXFYbVaycjIwGq1\nYjabSUlJwc7OjlatWvHDDz9QXFzMK6+8QkJCAlVVVVitVhRFQQjBr7/+KvlctGiRtLmVK1fi4OCA\n2WwmKSkJAB8fHxo0aMDu3bt56aWXCA8PJz4+nhs3bnDmzBnWr18v51VeXk5CQgJ//vknbdq0ITEx\nkaqqKvr27YuiKFgsFnQ6HcXF
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 287
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Finite Circuits and Turing Equivalence)\n",
|
||
|
|
"\n",
|
||
|
|
"problem:\n",
|
||
|
|
"\n",
|
||
|
|
"- neural networks are necessarily finite size\n",
|
||
|
|
"- Turing equivalence means that something needs to work for arbitrary sized inputs\n",
|
||
|
|
"\n",
|
||
|
|
"solution:\n",
|
||
|
|
"\n",
|
||
|
|
"- same as in circuit complexity\n",
|
||
|
|
"- we give a general rule for how to build circuits of all sizes\n",
|
||
|
|
"- we give a rule determining from the input size how big a circuit should be constructed to solve the problem\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"We start off with defining a size for the input, a number of iterations to run, and an initial random boolean vector.\n",
|
||
|
|
"\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"N = 100\n",
|
||
|
|
"niter = 100\n",
|
||
|
|
"vstart = 1.0 * (rand(N)>0.5)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 274
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Encoding Rule 110 as Matrix Operations)\n",
|
||
|
|
"\n",
|
||
|
|
"The idea behind encoding Rule 110 as matrix operations is the following:\n",
|
||
|
|
"\n",
|
||
|
|
"- we observe that there are only two cases where the output is zero\n",
|
||
|
|
"- all bits in the 3-neighborhood are 1: $111$ $\\rightarrow$ zero output\n",
|
||
|
|
"- the two rightmost bits are 1: $?00$ $\\rightarrow$ zero output\n",
|
||
|
|
"\n",
|
||
|
|
"Given a vector $(...,x_i-1,x_i,x_i+1,...)$, we can test whether all three bits are 1 by computing a dot product:\n",
|
||
|
|
"\n",
|
||
|
|
"$$ (0,...,0,1,1,1,0,...,0) \\cdot (...,x_i-1,x_i,x_i+1,...) \\geq 3 $$\n",
|
||
|
|
"\n",
|
||
|
|
"We can do this for every 3-neighborhood by constructing a _circulant matrix_.\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"# counting the number of bits\n",
|
||
|
|
"Mall = linalg.circulant(1*(roll(arange(N)<3,-1)))\n",
|
||
|
|
"imshow(Mall,interpolation='none',cmap=cm.gray)\n",
|
||
|
|
"print 1*(dot(Mall,vstart)>=3)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "stream",
|
||
|
|
"stream": "stdout",
|
||
|
|
"text": [
|
||
|
|
"[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1\n",
|
||
|
|
" 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
|
||
|
|
" 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0]\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAP0AAAD8CAYAAAC8aaJZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAEN5JREFUeJzt3V9oU+cbB/DvOTUXQRyiM+k0FcU1adM6W6cI3kwXTgdi\na2fL2IQq4ryRgYps88r9ubApXswKu/JCwgR1V05EZZYiCP4ZEjdlK1TEsKBJLtqGUe1sevLuwiU2\nNn+bnOQk7/cDL/yaxOQZ/J5+33PO0xNFCCFARNJQK10AEZUXm55IMmx6Ismw6Ykkw6Ynkgybnkgy\nRTX9tWvX0NTUhMbGRgwMDJSqJiIykDLf6/S6rsPlcmFoaAgrVqzAxo0bce7cOTQ3N5e6RiIqoXkn\n/W+//YZ3330Xq1atgsViwaeffopffvmllLURkQEWzPcfPn36FA0NDcmfHQ4H7t69m/IaRVHmXxkR\nFSXTJn7eTZ9vQ3/wwQfYsmULAOC7776b78cRUQaKoiQb/JtvvgGQvdfm3fQrVqxAMBhM/hwMBuFw\nOOa8bsuWLfj2228BAMeOHQMA1NXVzfdjiegNsxP9+++/h9Vqzfr6eR/Tb9iwAY8ePUIgEMD09DQu\nXLiArq6u+b4dEZWLKMKVK1eE0+kUa9asEcePH5/zPAChKMqcx3VdTy4AXFxcJVxWq1UAmVt73pfs\n8qEoClRVha7rKY/H4/Hk/+ZWn6i0rFYrpqamSn8iL1/xeDzZ2InmV9XXRxWJx9j8ROXBMVwiybDp\niSRj+PYeeH0M/+Y2H3i91ec2n6g8mPREkilL0ie8mfjA3JN7THwiYzHpiSRT1qRPSHedPlPiz34N\nERWPSU8kmYok/WyZzuxzgIfIGEx6IslUPOkTeC2fqDyY9ESSYdMTScY02/sEDvAQGYtJTyQZ0yV9\nAgd4iIzBpCeSjGmTfjYO8BCVDpOeSDJVkfQJHOAhKh6TnkgybHoiyVTV9j6BAzxE88ekJ5JMVSZ9\nQiEDPEx8oleY9ESSqeqkny3XAA9HdoleYdITSaZmkj6BI7tE2THpiSTDpieSTM1t7xM4p0+UHpOe\nSDI1m/QJHNklSsWkJ5JMzqYPBoPYunUrWlpa0NrailOnTgEAxsfHoWkanE4nOjo6EI1GDS+2GPF4\nPLnq6upSUl1VVaiqCl3Xk4uoVilCCJHtBeFwGOFwGG1tbZicnMT777+Pixcv4syZM3j77bfx1Vdf\nYWBgABMTE/B6valvriiGFj9f6ab0gPSz/ETVxmq1YmpqChlbWxRox44d4vr168LlcolwOCyEECIU\nCgmXyzXntQBMvVRVFaqqpv3v1HVd6Lpe8Rq5uApdVqtVAJlbu6Bj+kAggPv372PTpk2IRCKw2+0A\nALvdjkgkUshbEZFBYrFY1ufzbvrJyUn09PRgcHAQixYtSnlOURTTbuWzyXSMD8w9zieqFhaLJevz\neTV9LBZDT08P+vr60N3dDeBVuofDYQBAKBSCzWYrslQiKoecTS+EwL59++B2u3Ho0KHk411dXfD5\nfAAAn8+X/GVARCaX68TdzZs3haIoYt26daKtrU20tbWJq1evirGxMeHxeERjY6PQNE1MTExU3Ym8\nN1fixF66k3s8scdVLSvXibycl+yKUW3H+en+/DYh3WQfkRnlumRX82O4heCXZpIMOIZLJBkmfQa8\nAw/VKiY9kWSY9DnwZhxUa5j0RJJh0xNJhtv7PPEOPFQrmPREkmHSF4hfmknVjklPJBkmfRH4pZlU\njZj0RJJh0pcAR3apmjDpiSTDpieSDLf3JcQ5faoGTHoiyTDpDcCRXTIzJj2RZJj0BuI998iMmPRE\nkmHSlwkHeMgsmPREkmHSlxmv5VOlMemJJMOmJ5IMt/cVwgEeqhQmPZFkmPQVxgEeKjcmPZFkmPQm\nwgEeKgcmPZFkmPQmxAEeMhKTnkgyeTW9rutob29HZ2cnAGB8fByapsHpdKKjowPRaNTQIomodPJq\n+sHBQbjdbiiKAgDwer3QNA2jo6PweDzwer2GFimreDyOeDyOurq65EpQVRWqqkLX9ZTtP1FOIodg\nMCg8Ho8YHh4W27dvF0II4XK5RDgcFkIIEQqFhMvlSvtvAXCVYKmqmlxv0nVd6Lpe8Rq5zLOsVqsA\nMrd2zqQ/fPgwTpw4kXLZKBKJwG63AwDsdjsikUiut6EiJBJ/duonMPGpUFmb/vLly7DZbGhvb8er\n4J5LUZTktp+IKi8Wi2V9Puslu1u3buHSpUu4cuUK/v33X/zzzz/o6+uD3W5HOBxGfX09QqEQbDZb\nSYumzPilmZSLxWLBzMxM5hfkOqZPuHHjRvKY/ssvvxRer1cIIUR/f7/4+uuveUxf5pXrGJ/H+fKu\noo/pZ0ts448ePYrr16/D6XRieHgYR48eLeRtqARyHePzOJ8yUUSmg/VSvDmP9Q2XblufkO5v9qn2\nWa1WTE1NZTwPx4k8Islw9r7KcU6fCsWkJ5IMk75G8J57lC8mPZFkmPQ1hvfco1yY9ESSYdLXMN5z\nj9Jh0hNJhkkvAV7Lp9mY9ESSYdMTSYbbe4lwgIcAJj2RdJj0EuIAj9yY9ESSYdJLjgM88mHSE0mG\nSU8AOMAjEyY9kWTY9ESS4faeUnCAp/Yx6Ykkw6SntDjAU7uY9ESSYdJTThzgqS1MeiLJMOkpbxzg\nqQ1MeiLJsOmJJMPtPRWMAzzVjUlPJBkmPc1bIQM8THzzYNITSYZJTyWRa4CHI7vmwaQnkkxeTR+N\nRtHb24vm5ma43W7cvXsX4+Pj0DQNTqcTHR0diEajRtdKVSAejyMej6Ouri4l0VVVTS5d11OSn8or\nr6Y/ePAgtm3bhpGRETx48ABNTU3wer3QNA2jo6PweDzwer1G10pEpSByiEajYvXq1XMed7lcIhwO\nCyGECIVCwuVyzXkNAC5Jl6qqQlXVtP+f0nVd6Lpe8RprdVmtVgFkbu2cSf/kyRMsW7YMe/fuxfr1\n67F//348f/4ckUgEdrsdAGC32xGJRHK9FUkk0zYfALf5FZaz6WdmZuD3+3HgwAH4/X4sXLhwzlZe\nURQoimJYkUSUv1gslvX5nE3vcDjgcDiwceNGAEBvby/8fj/q6+sRDocBAKFQCDabrQTlUq15M/HT\nndxj4peWxWLJ+nzOpq+vr0dDQwNGR0cBAENDQ2hpaUFnZyd8Ph8AwOfzobu7uwTlEpHRlP9PuGX1\nxx9/4PPPP8f09DTWrFmDM2fOQNd1fPLJJ/j777+xatUq/Pzzz1i8eHHqm3PLT2mkG9gB0o/1UuGs\nViumpqaQqbXzavr5YtNTOmx6Y+Vqeo7hUtnxnnuVxTFcIskw6alieM+9ymDSE0mGTU8kGW7vqeJ4\nz73yYtITSYZJT6bBL80sDyY9kWSY9GRKHOAxDpOeSDJMejI1DvCUHpOeSDJseiLJcHtPVYEDPKXD\npCeSDJOeqgq/NLN4THoiyTDpqWrxSzPnh0lPJBkmPVU9juwWhklPJBk2PZFkuL2nmsE5/fww6Ykk\nw6SnmsOR3eyY9ESSYdJTzeI999Jj0hNJhklPUuAAz2tMeiLJMOlJKryWz6Qnkg6bnkgy3N6TlGQe\n4GHSE0kmZ9P39/ejpaUFa9euxa5du/Dy5UuMj49D0zQ4nU50dHQgGo2Wo1aikovH48lVV1eXkuqq\nqkJVVei6nly1IGvTBwIBnD59Gn6/Hw8fPoSu6zh//jy8Xi80TcPo6Cg8Hg+8Xm+56iWiImVt+rfe\negsWiwUvXrzAzMwMXrx4geXLl+PSpUvYs2cPAGDPnj24ePFiWYolMlKuxJ+d+tUsa9MvWbIER44c\nwcqVK7F8+XIsXrwYmqYhEonAbrcDAOx2OyKRSFmKJaLcYrFY1uezNv3jx49x8uRJBAIBPHv2DJOT\nkzh79mzKaxRFgaIoxVdKZBKZEh+Ye5xvRhaLJevzWZv+3r172Lx5M5YuXYoFCxZg586duH37Nurr\n6xEOhwEAoVAINputdBUTkaGy
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 275
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"With the same idea, we test whether the two rightmost bits are zero.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"Mlo = linalg.circulant(-1*(arange(N)<2))"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 276
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"We can now put these two ideas together and compute vectors $v_{111}$ and $v_{x00}$ that indicate whether we are in a $111$ or $x00$ neighborhood.\n",
|
||
|
|
"\n",
|
||
|
|
"We can then compute another threshold function to compute the NOR of these two vectors to get the final output."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"# Rule 110, two steps\n",
|
||
|
|
"v = vstart.copy()\n",
|
||
|
|
"result = []\n",
|
||
|
|
"for i in range(niter):\n",
|
||
|
|
" result.append(v)\n",
|
||
|
|
" v111 = (dot(Mall,v)>=3)\n",
|
||
|
|
" vx00 = (dot(Mlo,v)>=0)\n",
|
||
|
|
" on = (-1*v111-1*vx00>=0)\n",
|
||
|
|
" v = 1*on"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 277
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"This actually looks quite nicely like Rule 110 ought to look.\n",
|
||
|
|
"\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"imshow(array(result),interpolation='nearest',cmap=cm.gray)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 278,
|
||
|
|
"text": [
|
||
|
|
"<matplotlib.image.AxesImage at 0xf7d2bd0>"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAP0AAAD8CAYAAAC8aaJZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHxFJREFUeJztnW9ondUdx7+R9MUYG7HO3GBTSeeapEnVtrMTfLGlhptC\nMTVrS+eEroj6ZgysCGMMRuObJp0vtop75YZcOrDrq66IKzO4gEPbTeJUZke2kdCsJhdmenFV16bh\n7MWWu9snz/l/zvM87f1+4EJy7/n9ec7znOf3O+f8nntbhBAChJCm4Za8HSCEZAsHPSFNBgc9IU0G\nBz0hTQYHPSFNBgc9IU2G16A/c+YMent7sXHjRhw9ejSUT4SQiLS47tMvLy+jp6cHExMTWLduHbZv\n346XX34ZmzZtCu0jISQgzpH+D3/4A77yla+gq6sLa9aswSOPPIJf//rXIX0jhESg1VXw4sWLWL9+\nff3/zs5OnDt37ro2LS0t7p4RQryQJfHOkT70gBZCFOZ1+PDhYLpUxyfrA5P+aSSkvyq/itrHpv0t\na2Mik+avzXVt0qcunyWvg5WXCudIv27dOszNzdX/n5ubQ2dnp6s6Qogno6Oj9b+fffZZeUPhyNLS\nkvjyl78sZmZmxJUrV8S9994rPvjgg+vaABCHDx8WALSvRpmb4WWDSsZE3+HDh4P0nc523n3q0t++\n58TEjk+fxkJlwzm9b21txQsvvICdO3eir68P3/rWt1JX7gcGBlxNEEPYx8QG5y07I+UtLRBCGM3/\nV9y4WRb/bLp15ZjTZFSfydq6krSRtF3kcyPrn0afXc6JiR1Vv+j6NBYrYy/1sywGfeP/Mmw7s+iY\nDBSXrk/TJ7uwbAkxKPIi2d+qY/EZ0LZ6s7hZy5DZZhkuIU2G8+q9C6ZRP9m+aFHFBpNjsOkLmwzC\ntd9MImFRz40q67Hpw6RMWttkVmHSNs3PrPuSkZ6QJiPThTyThSrVwkvRoooKl4Ul3/m/ST+r0Pnj\nMk/OCps5fZI0mVgLbj5rDrZwTk8IAZDx6n1IvUUnRORR6Uv7zFW3To9NJMzr3JhkVqYytnpMMIns\nofuSkZ4QAoCDnpCmozAVeSbcSAU8odJNk9TPpRDIZArhe2lkeW5MfJctTPr2Wyj/VLjYZXpPCAFQ\noDJcE4q8ZZTEJ/L4YrPYZ1KbbtO3eWVjIZ51sF0k9e0XnR7fvmSkJ4QAKHgZrgzf0sosUd3hZT77\nzhtdSkdN2oSaz8bEZH4uOyeq6zMtO3A5Ll89IfqSkZ6QJqMwZbgm3EiPfoZ6tDZW/6TpD9G/eRXw\nuOxO6HTYEroQyLcvOacnhADgoCek6ShM7X2oRYyiFPD4pJu+T8m5PFFnYivGtmPsJ8psnmp0XWgO\nMbVI02OL6blgpCekychky85mG8U2St0o38Bj8pRcqG/DsWmbxTfLyGRsbZlgsiVpYtvHL9X1aaLX\nNcsw9ZmRnpAmI/cyXJu5pc0zya7fUBOKUA+vxCoZjbWF5GvbtwDIRl+oLeBQD9O4XKeq4+acnhAC\nIINID5iVerq0lbW39S8GPg+v+EYK17708cMk8whVdJKGzwNOvo/WhtoJUWFTDKWzwUhPSJPBQU9I\nk5Fbeh/LlglZFPC4pJtJWdM2oQid/obyMfSUKPTiqM/UQmbXRY/MrySM9IQ0GZlG+ryertLJ2Mqb\n4LMIFipSmGATKWwjoUrOxy9V+1hPuoXKWl2zARs9K58z0hNCAOT4wE2WD1rIZGIW8PjMh13v8KEi\nqgkmWZxPn9pmYyEeegm1jear27UYqrENIz0hpE4mc/oVYqya+66c6ghVFuo7H47ls83agO38PVSB\nkskag4kt3TkJtaKukou15pD2OSM9IQQABz0hTYd20M/NzWHHjh3o7+/H5s2b8fzzzwMAFhcXUS6X\n0d3djaGhIdRqtVR5XcoihAhSxKHSI/uspaVF+krK+vqo0iGznSZn43NIH019Tusv3z6VtfW15XLN\nZNHW9RynXT+p+nVz+oWFBSwsLGDLli24fPkyvvrVr+LUqVN46aWX8KUvfQnf//73cfToUVy6dAnj\n4+OrnFhZSVxxVHWgLoTYezXVG2K1Nm2O6bI/a2LTtWYh5MMdjW1dbdngswYSau88jRC7C6b2dav3\nEJY8/PDD4rXXXhM9PT1iYWFBCCHE/Py86OnpWdVWpR5A6ucr75u+TORMsJFx8cvGB917Mh9cfLaR\nMfHZtt9NbNn0t06vr3+692Q2bXXr9Jgctwyrr8uanZ3FO++8g/vvvx/VahWlUgkAUCqVUK1WU2VG\nR0frfw8MDGBgYMDGJCHEgMnJSUxOThq1Nd6yu3z5Mr7xjW/gRz/6EUZGRnDrrbfi0qVL9c/Xrl2L\nxcXF65V7bJWlyaeR1GmTNqX5o5oCmNhS6db554pNyajJNpXsOF39DFWgZFNwZXPsobbR0ghVzusy\nRZa1NVq9X1pawt69e3HgwAGMjIwA+G90X1hYAADMz8+jvb3dRBUhJGe0g14Igccffxx9fX04dOhQ\n/f3du3ejUqkAACqVSv1mYIpudXLFtu0dUSVjoi/ZZuX/NDkTfTaryapVW5t+cu0Dm+O08dHmPIY+\nfyaf2ZzHGOfGRY/PeNGm97///e/x9a9/Hffcc0/dyNjYGL72ta9h//79uHDhArq6unDy5Em0tbWt\nOpikU7LP0tro2sraJ2VCp6sqW0mbJummSZop0+9KzJR9BZupl69tGz26aUya3pjnxmUHw+a6WvW5\n6ZzeBQ56DnqdDAd9Ew16mzayto3ts7iIZbbTdPh0q+2ACnVB6vTEvCH73kRCL8rZ3BhUdnyCm8ki\nq4yWFtbeE0L+R+6/T9/YNtnG5G5rEk1k2EYuE/nQ+kJNg5JyLltjWWRhoSO1yh8f/bZ6XDJa16xs\nZcwx0hNCAGQU6WWfAeEX02JGLpm8ycKSa+Yhk/eJAqa4zDFds7BQi2o2/sRaaA6V0erkZH4y0hNC\nriP31XtZW1OyjFw6275rDWmRzGS7MfQWVOgtTp/tJVWb0FuAeUVxG39M5RjpCSF1clu999kHbSTL\nyGVz1zex5aLPldDR0neNQqfXJ8o1/q/CN/r6RHFbf2zXpRjpCSF1OOgJaTJy27IzldcRO101WXwK\nXQvuuqjp44OJH65luKG3K01kdLKN8jELgmR6XIuZbLYZmd4TQgBkvJBngms0Ucn4RC7XO32oKOIT\n9V2LTWQ+uJbh6nxobBszyunaxCgIUvmTbB9qW0+nj5GekCYj0zl9jLmdSYSQ6XEttJD5YGIzTc53\n7iwj1pywsW2sMlwVsYp9TNr4RnHXrMnEVlIHIz0hBEBGZbg2kcu2gCdUNHHJFJJ6bee1LkVDvusj\nJrZcopMKF1tp+BT7qORDFwT56km+30iIHRFGekKaDA56QpqM3NL7ZJsVskwhQ21BuS4omeDzjIJv\nnbiJX6b2Q+gPXewTqyAoph6XbdAkjPSENBmZRnrbRazY0URnP+lD7JJiVzsu0STWFmBa+1DFWT7F\nPjLdKv1pNly3cEPpUcEyXEJIKrnP6W30pOESTZKyIf3R2XCdi+v0prW13f608Utn29VWqHOSR9mr\nr+3QWQUjPSEEQI5zehNcSiBdI5dLFIpRViyTiR3JVP6k2QxdOJWUce1bm3UkG39MUK1LZZ1VsAyX\nEFKHg56QJiP3H7tQYSIbWr9LqmeTrsZI3UMXm4TaQkrqcz32rPxxLQhySd1D6ZFdB0zvCSF1cv+x\nC98omdQTKlKY3PVdFhpVFGkhSNc29Pabb8l2Vv6EygZiZxWM9ISQOoX7qepGfOb0JjZCbUGpbN2o\nc0JdWxt/fNdJsvLHdYvTN+OLkVUw0hNC6hgN+uXlZWzduhXDw8MAgMXFRZTLZXR3d2NoaAi1Wk0p\nL4RIvYsl7+aqu35a22SUkr1MbMg+s7Gl0qeyHeoYfPXo+iANE39sfE7K5O2PzTk28T2UHpNjkGE0\n6I8dO4a+vr66s+Pj4yiXy5ie
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 278
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Single Recurrent Neural Network)\n",
|
||
|
|
"\n",
|
||
|
|
"This isn't quite a recurrent neural network yet.\n",
|
||
|
|
"\n",
|
||
|
|
"To get that, we pack together the vector $v$ with two variables representing intermediate states of the computation.\n",
|
||
|
|
"\n",
|
||
|
|
"If you work out the matrix multiplications, you'll see that this outputs a row of the original output every other step.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"Z = zeros((N,N))\n",
|
||
|
|
"v = concatenate([vstart,zeros(2*N)])\n",
|
||
|
|
"M = array(bmat([[Z,-1*eye(N),-1*eye(N)],[Mall,Z,Z],[Mlo,Z,Z]]))\n",
|
||
|
|
"b = concatenate([zeros(N),3*ones(N),zeros(N)])"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 279
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Weight Matrix)\n",
|
||
|
|
"\n",
|
||
|
|
"This shows the weight matrix of the single layer recurrent network for Rule 110.\n",
|
||
|
|
"Note that all the green entries are 0.\n",
|
||
|
|
"We can greatly speed up such computations using a _sparse matrix package_."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"\n",
|
||
|
|
"imshow(M)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 280,
|
||
|
|
"text": [
|
||
|
|
"<matplotlib.image.AxesImage at 0xfb4dd90>"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAQMAAAD9CAYAAAC4PhIWAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XtclHX+9/HXNRe47Ya62C5IMwgqIKKIpKHbpquraHhA\nTSXZNLbs/pV2WNOOj6zV7gra3bbUtMzclrZ7UzsobgnSiVB3i1KsXSlFBUNE1hPl4dfCzPW9/wBp\nLWBGmJlrZvg8/4KZC67PfJl58/1cR00ppRBCdHoWswsQQvgGCQMhBCBhIIRoImEghAAkDIQQTSQM\nhBCAh8KgoKCA+Ph4YmNjeeKJJzyxCiGEm2nuPs7A4XDQr18/3nnnHaxWK1deeSWvvPIK/fv3d+dq\nhBBu5vaZQUlJCTExMURHRxMcHMysWbPIy8tz92qEEG7m9jCorq4mMjKy+XubzUZ1dbW7VyOEcLMg\nd/9CTdPcsowQwjNa2zLg9jCwWq1UVVU1f19VVYXNZvvecovVA+5edYcUL9nGyCUjzC7je4qXbGPA\nr0by0VM6E561m10O4JtjVbxkGyMeGsHHz+hYhxtYh5l/yo0vjtOjWnarz7m9TRg6dCjl5eVUVlZS\nX1/P+vXrSU9Pd/dqOpXL4hQDMx3sfNaCnFbWOk2HlN84KH1B59gemX1eLLeHQVBQEM888wzjx48n\nISGB6667TvYkuEGvkYquNiharJtdis+btMbO3jwL+/4mh9FcDLe3CQBpaWmkpaV54ld7TNSoXmaX\n0KL/ritussFPB2jkzw8ibZV5LYMvjtV3a/r5fQ5Klusc+UTj8qHmTKd8cZza4vbjDFxaqab53DYD\nf3KoyMKJL+CKWw2zS/F5b/2fIIbe7iA8SforaNxm0NpHXuZRfihqlEGIFd69T1oGZyausXMg30K5\ntAxOyQj5qbjJBkPnG+TP90inF1CG3+PgxF6No6WyUbEtEgZ+rHuUov8Mg12r5c/YFosOw+928MlK\nXQKhDfIu8nPRvzToaoV3FknL4MykF+xUvit7GVojoxIAYicZpNxlUHCbBIIzKXc5OF6mUfupzBC+\nS8IgQHSzKfpNU+x6Xv6kbbHocNV9Dj55pnG3o/iWvHMCSO+xBt1s8PZdMkNwZuIaO1XbpGX4bzIS\nASZmgsGwhQZb75BAcCblTgf//kyTQ5ebSBgEoG6RithJilJpGdqk6XD1gw4+elqn+iMJBHm3BKg+\n4w26RkLhApkhODNpjZ3qDy2Uv9m5Pw6d+9UHuJg0g5/dY7D1TgkEZ6683UHNTo0TX3TeGYKEQYDr\nalXETFCUrpE/dVs0HUb+1sGHf9Q5/PfOGQjyDukE+l5j0C0SmSG4YOLzdmp2ds6WofO94k6q7zUG\nV91nyDYEFwy9zcGREo2T+zvXDEHCoBPpalX0GSctgzOaBX7xiIN//E6nanvnCQR5V3QyMRMMuveC\nAjkOwamJz9up/dRC+Vud42PSOV6luECf8QY/v8+QIxVdMGSeg6rtGl9VBv4MQcKgk+pqU/ROlXMZ\nnNEs8MtsB9sf1/myOLADQd4JnVjMBIPQPsjZji6Y+LydY3s09gdwyxC4r0y4pPdYg6seMOR6CC4Y\ncqtBZZHG11WBOUOQMBB0symiRiu5YpIzGoz9vYPtj+kcej/wxirwXpFol9hJBqExUHCbXFPRmQnP\n2Tn+BezPD6yPT2C9GtEhvccY/OxeB+/eKy2DM0PmGRzcqnGmJnBaBgkDcYHuUYpeIxW7npO3hjPj\nnnZQvFSn8r3AGKvAeBXCrWInGVwWj1yG3QUTnrNzch8cCICWwf9fgfCIqFEGw+928P6Dutzs1Ykr\nbjU4UOD/LYOEgWhVaB+Fdbi0DK4Yt8zBtv+rU/GO/45VhyqPjo5m0KBBJCcnk5KSAsDJkydJTU0l\nLi6OcePGUVdX55ZChTkab/aq2DJPWgZn0lbZOXUADmz1z0DoUNWaplFUVERpaSklJSUA5OTkkJqa\nyr59+xgzZgw5OTluKVSYp9dIxbC7HBQv0VFyr9c2XXGLQfmbGmeO+l/L0OEI++4dXTdv3kxWVhYA\nWVlZbNq0qaOrED7gsjhFz2TFzmdlt6Mz16xobBkOvu1fM4QOzwzGjh3L0KFDWbNmDQC1tbWEh4cD\nEB4eTm1tbcerFD4hbopBeJLBllulZXAmbaWduoP4VSB06K+6Y8cOIiIiOHbsGKmpqcTHx1/wvKZp\naFrL06XiJduav44a1YuoUVEdKUV4SeTVih9e1vif7+oHHWj+8173uituMci/LYiwgYqQCHN2yRwq\nOsShoi9dWlZT353nt9PSpUsJCQlhzZo1FBUV0bNnT2pqahg9ejRffPHFhSvVNBarB9yxWmGSfZst\nfHVI48o7HGaX4vO23qETM0nRd7z5G1we1bK/19qf1+5cP3fuHKdPnwbg7NmzFBYWkpiYSHp6Orm5\nuQDk5uYyderU9q5C+LC4dIOIodIyuGL8CgdfVeLzux3b/Zesra1l2rRpANjtdq6//nrGjRvH0KFD\nycjIYO3atURHR7Nhwwa3FSt8i+1nii4hDnZk61x1rwNNti226opbDPLnB/HTAea1DM64rU24qJVK\nmxBQ9uZZ+KpSI+U30jI4s/VOnZgJir7XmNMyeKRNEOK8flMMrMOlZXDF+OWNLYMvntzkexUJv2Qd\nphhya+PlxZVMENp0xa0GZRssPncug4SBcJvwwYrL+ik+WiYbD5yZ8Jydvz9hYf8W3/kI+k4lIiDE\nTTGI+oXBllukZXBm3NMOvvoSn7mEmm9UIQJKxBBF8v803sRUWoa2DbnVYM96i09cZFXCQHhExBBF\nj76KD5+UlsGZCc/ZKVluMf0y7BIGwmPiphj0TpW9DK4Y+zsHXx3C1Bu1SBgIj+qZrEi60UHJ09Iy\ntEmDIfMN/vmybtqt3CQMhMdZhyl+3Fvx999Jy+DMxOft7Fxtzs1eJQyEV8RNMYidJC2DK0Y/5uCr\nSs3rt4OXMBBeE5aoGJTl4OMVcsWktmgWGHqbg89e0jm533uBIGEgvMr2M0X3KMX2x6RlcGbi83b+\n+ZKF8je98zGVMBBeF5du0H+GtAyuGLnEQV2FxuG/e36GIGEgTPGT/orE2Q4+WSktQ1s0C1x5h4NP\nX9Q5sdezgSBhIEwTebWim02x7RFpGZyZuMbOnnWebRkkDISp4qYYDPiVIfdlcMGIxQ5OHdCo/sgz\nMwQJA2G6y+IUAzMd7HzWIrdya4OmQ8pvHJS+oHNsj/sDQcJA+IReIxVdbVC0WFoGZyatsbM3z8K+\nv7n34ythIHxG3GSDwXMNufuzC35+n4NT+zWOfOK+GYKEgfApoX0UCRmG3OzVCU2HYXc5KF2tU/up\newJBRlz4nKhRBiFWePc+aRmcmbjGzoF8C+VuaBkkDIRPiptsMHS+tAyuGH6PgxN7NY6WdmyGIGEg\nfFb3KEX/GQa7VsvbtC0WHYbf3XgAV0cCQUZZ+LToXxp0tcI7i6RlcGbSC3Yq323/XgYJA+HzYicZ\npNxlUHCbBIIzKXc5OF6mtWujooSB8AvdbIp+0xS7npe3bFssOlx1n4NPntEverejjKzwG73HGnSz\nwdt3yQzBmYlr7FRtu7iWQcJA+JWYCQbDFhpsvUMCwZmUOx38+zPN5UOXJQyE3+kWqYidpCiVlqFN\nmg5XP+jgo6d1l05ucjqaN910E+Hh4SQmJjY/dvLkSVJTU4mLi2PcuHHU1dU1P5ednU1sbCzx8fEU\nFha282UI0bY+4w26RkLhApkhODNpjZ3qD52f/uw0DG688UYKCgoueCwnJ4fU1FT27dvHmDFjyMnJ\nAaCsrIz169dTVlZGQUEB8+fPxzDkyhXCM2LSDH52j8HWOyUQnLnydgc1O9ueHTgNgxEjRhAaGnrB\nY5s3byYrKwuArKwsNm3aBEBeXh6ZmZkEBwcTHR1NTEwMJSUlLf/ig3UtPy6aabuOml2Cz+tqVcRM\nUE7f6J2dpsPI37Z944p2HetZ
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 280
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"After this packing, the entire inner loop is a simpler recurrent layer of linear threshold units.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"result = []\n",
|
||
|
|
"for i in range(2*niter):\n",
|
||
|
|
" result.append(v)\n",
|
||
|
|
" v = H(dot(M,v)-b)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 281
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"result = array(result)\n",
|
||
|
|
"imshow(result,interpolation='nearest',cmap=cm.gray)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 282,
|
||
|
|
"text": [
|
||
|
|
"<matplotlib.image.AxesImage at 0xfcf7910>"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAXIAAAD9CAYAAAChtfywAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJztnV+IXdX1x9do5i22VTTjMCOM5s/EmDgRrPVFaNDoU1PF\notFWpWopvpVKU/oU86AmD32wtoVSKuSpti82fdA0FJI2SGGkVZDmwUDHdhwnoZoI/oFGZf8eftzL\nmZ29/u597jn7uj4wOHPO3mutvc+5+3z3WufGiRBCAMdxHKdaLuk6AMdxHCcPX8gdx3Eqxxdyx3Gc\nyvGF3HEcp3J8IXccx6kcX8gdx3Eqp/hCfvToUdi6dSts3rwZDh06VNq84ziOEzFR8j3yzz//HObn\n5+HPf/4zzMzMwFe/+lX47W9/C9dff30pF47jOE5EUUW+uLgImzZtgrm5OZicnIS9e/fCkSNHSrpw\nHMdxIoou5CsrK3DNNdcM/56dnYWVlZWSLhzHcZyIdSWNTUxMFGnjOI7jXAyWCS+qyGdmZmB5eXn4\n9/LyMszOzor6hhBG8hP7a/6dikUT24D9+/e3HnczNirG1Dyn5h37PfV3G+Pry884jy11PzhjQijI\np59+Gq677rqwtLQU/ve//4WFhYVw6tSpNW0AwH/G9Kdt2oytzbGkbEtiHOV16vq+4eZG+rN///5O\nx8LNt+Q+0F67EEIoqsjXrVsHP//5z+Guu+6Cbdu2wf333y9+YyWMQC0EQqWkfo/bSGwD/L8ibzNu\naYyp4xI71A/FxMREqz85aG23GTc2lpLjxcDuTe19UPKn6T83lq7Hwn1mcmKlKPr6oQTsBg0htJ4/\nx4Y6MTExPNf8PW4jsT0xMQHHjx+HXbt2ZUZ7se1mLJIYmzGlbGF2KLzGUTfHjx+Hr3/9612H0Ron\nTpwY2/FRn9feLOSOIyH1UOPa9uGekzxUc21LGPjB5rHN5SD3OlCxpWyXGosmbuyalroXe7WQp9T3\nKD50lN8U8c0tWTRS/XNpxq25UVJt24zT6T8j/rg7BXFF7ow1GpUutTNqQaFp24aSxwRASSwKNR4/\nlR7F+udi2fVh1y0nzt4t5G1uMykwhcp9UCSxYTdcibFQOXJqqzyIKc7/txWn039ckddL7xZyp24w\nZTGKgrWVrmOTpudGHSOlKEtDKVSNkKPSg22MR7trkCLdbTTj6N1CnlKUmFovhUTZptpRbeM+XDHJ\nGjeX447nT4J0t+GMD67I66WXC7njWNA86HNFQVsKWZqqw9DkXnMovTRoXuHloIQStWO0MMo1i7vu\nvVrIpS5LT6BE2TbPad70SOXVSyle7qZNoXnDpu2dkNMfXJHXC7V2+v8hyHEcp3I8teKokb4qNco4\nNAUy6ZtHJZHUV6jYMJttz3PJ5UGaMpGkSZrnpbab7TVIamIaX5Zi7qBfr1IrEtrY6ktSFKl0CFVd\nxoq1GLnVbaxITMWWsjc4L0kbOeODp1bqpcqF3HFSjCKXb1VSXWFR9BrBUWqJsCpbrq12Z6Idj2QH\np3nt0VLMHfTr1UIumfg2XovjlC0H9+UbLl7rIiTZamlee5TuTJzxwxV5vfRuIXe+GIwihxv7w8CU\nkiYfWzK2El8yyY1XM19cewklahPStpwS1n7fIic2jbiSvA2XjLHL1w+5QkHpL6xwylZaVMFeY5R+\naQg7T/mWbtlS+W9qEbMoeqdeXJHXS+8WcqduRq20Y99NSsTRhiKU2hpQuqifmyu3fFGJw6qkpX05\nWxIxxPkukR7V7ky4lxMAOlzIuQlpo+AkUbaWG1j69ke8y7B82CRvq2Axcm2bu422FhmnW1yR1wu1\nkPsXghzHcSrHUytOa4wq3y7d4WgKYF3cpzlpjtL1I8sXXTikKYqS323g5kjztlqzjzSzkPKV812S\nXqVWNGmI+FiqrRQuRcHdXJoCJvZWRIwlb4gVKaWvPUpj08bp9B9PrdRL7xZyp266Vq6lsRYHLV9C\naXO+cutKmNBJ2bEsG5yy5V69S/mVij2J0JHGneqPxRf3x2pb2cXprhdyq6ItVcWmKsKSCccKmJgv\ny0WU3Cia1x4lxdNU/3FYtL/ouCKvF1fkTm/IfX1P8rZTydcD27hfLYKkdCyUMImPc22l5IgvjaDj\n5ko7nlzRWFrRJ2PsKkfObZUo1WhViNyENeOTxIPZwV7jo2zGduO4sXaSm48tlCgVvVMvrsjrxRW5\nUwyq6KvJS5aKpYlG+WB2tOkl6RhLPSi1Y6b8a66lNB6KnJcU2njxIeeNGYn/HMGJ+e/VQp7KS6d+\np55ATXtSpIUSLGbJ2yKcQubGyH2wNP653QQW76gXZGd0uCKvF1fkTqe0kXu0pKG0Pqz920BSjAaw\n70pyY5PQZtpOqpA1uycuLkpgUT41O8C4DTbX/s1Ox3GcyunNF4K4Pim0OSjuCco9PSUxcqkOiT1t\nyif2n2qDFTSxeCVvLTj14amVevHUilOcnO30qClZZ+HslUr5tFWXyLFrKcJh7VN2JTUdLj4u1aGx\npY1BO7eW1EyvFnJrVdySa8LaxzE1z0sq+ym7EoXMxZqzU8CKxxgaRS+J3ek/rsjrxRW501ssKqbJ\nqO6nNtJL2qIX17bZR1t0w9CKJ8tuhYqPEkScXWmBGLM16jSjRjTGdP76IQe3ndMoRupmTj3tpLFa\nctiaajV2TPPaoyZeai78QVw3rsjrxRW5UwyLIhllsdT6sCmp9EcVg1TRW0QIZVcjRjBbOfeRJEas\nPyd+pDsZTS6+9L2Vorf/h6AB1KRpLyyndgfHLXa1OWzMXuoNE8lOgdttcMcluwosZqceXJHXiyty\np7eUUCvcAyvXbtzforhHsSvhXgyQPPRjSip9idrloOxarnep+4+LgTtujXeAfyHIcRyncjpPrcTH\nYySFuVR7SZEvtsEVVjm7lGqLn8gSFZmKhUvZaFRAbJdKtXixczzw1Eq9eGrFaQXpwt5Gsce65c+h\n1Hg1KYDc8Wj6S9IhXD9ODFA2NCIJs6t9S4yKPwdtzcryVluTzl8/lBb/4mOxzdQ5yYTFcWExcXax\n9rHi5T4sOePlxiMp8Kbi92Ln+OCKvF5ckTvFKFW041JVGiVoff3M4rPpV+sba299UFpiluwAmuSk\nF2N71nuGEzcliqhxP4nAxM5JfVja9G4hl1bJuXwup3wlWzJuCih1i/mkbGpz55LxYmPExkLFmTru\nD+DxwBV5vbgid1qhi8XeWiTO8VXKXlu+Neo0N2cci4rcndMoawDSmKRtNLntUvRuIZcWA7h8riR8\nTslbtjKpeDC/KXuS3YBk96Ip7kjilOTPnXpxRV4vrsidTrFW4qk+Fv+U3ZzdRdv2tXYkwoTLBZd+\neEtzwzGlajEpe7n5aq6t5ppbaxgD/AtBjuM4ldN5sZMq/A2OaQukTTRpGI264Z620io+Zx9rIylS\nSqr5XLE45cOpF0+t1EsrqZW5uTn40pe+BJdeeilMTk7C4uIinDt3Du6//37497//DXNzc/D73/8e\nvvKVr1wUjDO+cFvR3BRD6QeMpViWW6Br2hnQ1ueCE0fNdjmv8ZW6LtI3yzhxJRVW0v4aO5xNKp1l\nTa2YF/Jrr70W/v73v8MVV1wxPLZv3z648sorYd++fXDo0CE4f/48HDx4cK1D4sJIXuPTXiDpwsEp\naOq4tEg7OE699of1x+xI22NjSe0QqP7+IK4bV+T1QmYVgpG5ubnw3nvvrTk2Pz8fzpw5E0IIYXV1\nNczPz1/UDwD8Z0x+pNcz99p3de9wPrm4tPe99bMSt217rqgYpWOg2mmPS6+JZF4kc988L22PzZVm\nvlPzNsCsyK+77jr48pe/DJdeeil8//vfh+9973tw+eWXw/nz5wH+3yNcccUVw78H5L4+2Py7eSxu\n2zzPbWmoc5LjWKypnHXKHnZMopw1r3Om5kobpyvyujF+3J0eQK2X66xGX331VZienob//ve/sHv3\nbti6detFTrEPffO4ZmFIteX6
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 282
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"To extract the Rule 110 result, we just take every other output, and we ignore the intermediate results.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"imshow(result[::2,:N],interpolation='nearest',cmap=cm.gray)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 283,
|
||
|
|
"text": [
|
||
|
|
"<matplotlib.image.AxesImage at 0xfd1e910>"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAP0AAAD8CAYAAAC8aaJZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHxFJREFUeJztnW9ondUdx7+R9MUYG7HO3GBTSeeapEnVtrMTfLGlhptC\nMTVrS+eEroj6ZgysCGMMRuObJp0vtop75YZcOrDrq66IKzO4gEPbTeJUZke2kdCsJhdmenFV16bh\n7MWWu9snz/l/zvM87f1+4EJy7/n9ec7znOf3O+f8nntbhBAChJCm4Za8HSCEZAsHPSFNBgc9IU0G\nBz0hTQYHPSFNBgc9IU2G16A/c+YMent7sXHjRhw9ejSUT4SQiLS47tMvLy+jp6cHExMTWLduHbZv\n346XX34ZmzZtCu0jISQgzpH+D3/4A77yla+gq6sLa9aswSOPPIJf//rXIX0jhESg1VXw4sWLWL9+\nff3/zs5OnDt37ro2LS0t7p4RQryQJfHOkT70gBZCFOZ1+PDhYLpUxyfrA5P+aSSkvyq/itrHpv0t\na2Mik+avzXVt0qcunyWvg5WXCudIv27dOszNzdX/n5ubQ2dnp6s6Qogno6Oj9b+fffZZeUPhyNLS\nkvjyl78sZmZmxJUrV8S9994rPvjgg+vaABCHDx8WALSvRpmb4WWDSsZE3+HDh4P0nc523n3q0t++\n58TEjk+fxkJlwzm9b21txQsvvICdO3eir68P3/rWt1JX7gcGBlxNEEPYx8QG5y07I+UtLRBCGM3/\nV9y4WRb/bLp15ZjTZFSfydq6krSRtF3kcyPrn0afXc6JiR1Vv+j6NBYrYy/1sywGfeP/Mmw7s+iY\nDBSXrk/TJ7uwbAkxKPIi2d+qY/EZ0LZ6s7hZy5DZZhkuIU2G8+q9C6ZRP9m+aFHFBpNjsOkLmwzC\ntd9MImFRz40q67Hpw6RMWttkVmHSNs3PrPuSkZ6QJiPThTyThSrVwkvRoooKl4Ul3/m/ST+r0Pnj\nMk/OCps5fZI0mVgLbj5rDrZwTk8IAZDx6n1IvUUnRORR6Uv7zFW3To9NJMzr3JhkVqYytnpMMIns\nofuSkZ4QAoCDnpCmozAVeSbcSAU8odJNk9TPpRDIZArhe2lkeW5MfJctTPr2Wyj/VLjYZXpPCAFQ\noDJcE4q8ZZTEJ/L4YrPYZ1KbbtO3eWVjIZ51sF0k9e0XnR7fvmSkJ4QAKHgZrgzf0sosUd3hZT77\nzhtdSkdN2oSaz8bEZH4uOyeq6zMtO3A5Ll89IfqSkZ6QJqMwZbgm3EiPfoZ6tDZW/6TpD9G/eRXw\nuOxO6HTYEroQyLcvOacnhADgoCek6ShM7X2oRYyiFPD4pJu+T8m5PFFnYivGtmPsJ8psnmp0XWgO\nMbVI02OL6blgpCekychky85mG8U2St0o38Bj8pRcqG/DsWmbxTfLyGRsbZlgsiVpYtvHL9X1aaLX\nNcsw9ZmRnpAmI/cyXJu5pc0zya7fUBOKUA+vxCoZjbWF5GvbtwDIRl+oLeBQD9O4XKeq4+acnhAC\nIINID5iVerq0lbW39S8GPg+v+EYK17708cMk8whVdJKGzwNOvo/WhtoJUWFTDKWzwUhPSJPBQU9I\nk5Fbeh/LlglZFPC4pJtJWdM2oQid/obyMfSUKPTiqM/UQmbXRY/MrySM9IQ0GZlG+ryertLJ2Mqb\n4LMIFipSmGATKWwjoUrOxy9V+1hPuoXKWl2zARs9K58z0hNCAOT4wE2WD1rIZGIW8PjMh13v8KEi\nqgkmWZxPn9pmYyEeegm1jear27UYqrENIz0hpE4mc/oVYqya+66c6ghVFuo7H47ls83agO38PVSB\nkskag4kt3TkJtaKukou15pD2OSM9IQQABz0hTYd20M/NzWHHjh3o7+/H5s2b8fzzzwMAFhcXUS6X\n0d3djaGhIdRqtVR5XcoihAhSxKHSI/uspaVF+krK+vqo0iGznSZn43NIH019Tusv3z6VtfW15XLN\nZNHW9RynXT+p+nVz+oWFBSwsLGDLli24fPkyvvrVr+LUqVN46aWX8KUvfQnf//73cfToUVy6dAnj\n4+OrnFhZSVxxVHWgLoTYezXVG2K1Nm2O6bI/a2LTtWYh5MMdjW1dbdngswYSau88jRC7C6b2dav3\nEJY8/PDD4rXXXhM9PT1iYWFBCCHE/Py86OnpWdVWpR5A6ucr75u+TORMsJFx8cvGB917Mh9cfLaR\nMfHZtt9NbNn0t06vr3+692Q2bXXr9Jgctwyrr8uanZ3FO++8g/vvvx/VahWlUgkAUCqVUK1WU2VG\nR0frfw8MDGBgYMDGJCHEgMnJSUxOThq1Nd6yu3z5Mr7xjW/gRz/6EUZGRnDrrbfi0qVL9c/Xrl2L\nxcXF65V7bJWlyaeR1GmTNqX5o5oCmNhS6db554pNyajJNpXsOF39DFWgZFNwZXPsobbR0ghVzusy\nRZa1NVq9X1pawt69e3HgwAGMjIwA+G90X1hYAADMz8+jvb3dRBUhJGe0g14Igccffxx9fX04dOhQ\n/f3du3ejUqkAACqVSv1mYIpudXLFtu0dUSVjoi/ZZuX/NDkTfTaryapVW5t+cu0Dm+O08dHmPIY+\nfyaf2ZzHGOfGRY/PeNGm97///e/x9a9/Hffcc0/dyNjYGL72ta9h//79uHDhArq6unDy5Em0tbWt\nOpikU7LP0tro2sraJ2VCp6sqW0mbJummSZop0+9KzJR9BZupl69tGz26aUya3pjnxmUHw+a6WvW5\n6ZzeBQ56DnqdDAd9Ew16mzayto3ts7iIZbbTdPh0q+2ACnVB6vTEvCH73kRCL8rZ3BhUdnyCm8ki\nq4yWFtbeE0L+R+6/T9/YNtnG5G5rEk1k2EYuE/nQ+kJNg5JyLltjWWRhoSO1yh8f/bZ6XDJa16xs\nZcwx0hNCAGQU6WWfAeEX02JGLpm8ycKSa+Yhk/eJAqa4zDFds7BQi2o2/sRaaA6V0erkZH4y0hNC\nriP31XtZW1OyjFw6275rDWmRzGS7MfQWVOgtTp/tJVWb0FuAeUVxG39M5RjpCSF1clu999kHbSTL\nyGVz1zex5aLPldDR0neNQqfXJ8o1/q/CN/r6RHFbf2zXpRjpCSF1OOgJaTJy27IzldcRO101WXwK\nXQvuuqjp44OJH65luKG3K01kdLKN8jELgmR6XIuZbLYZmd4TQgBkvJBngms0Ucn4RC7XO32oKOIT\n9V2LTWQ+uJbh6nxobBszyunaxCgIUvmTbB9qW0+nj5GekCYj0zl9jLmdSYSQ6XEttJD5YGIzTc53\n7iwj1pywsW2sMlwVsYp9TNr4RnHXrMnEVlIHIz0hBEBGZbg2kcu2gCdUNHHJFJJ6bee1LkVDvusj\nJrZcopMKF1tp+BT7qORDFwT56km+30iIHRFGekKaDA56QpqM3NL7ZJsVskwhQ21BuS4omeDzjIJv\nnbiJX6b2Q+gPXewTqyAoph6XbdAkjPSENBmZRnrbRazY0URnP+lD7JJiVzsu0STWFmBa+1DFWT7F\nPjLdKv1pNly3cEPpUcEyXEJIKrnP6W30pOESTZKyIf3R2XCdi+v0prW13f608Utn29VWqHOSR9mr\nr+3QWQUjPSEEQI5zehNcSiBdI5dLFIpRViyTiR3JVP6k2QxdOJWUce1bm3UkG39MUK1LZZ1VsAyX\nEFKHg56QJiP3H7tQYSIbWr9LqmeTrsZI3UMXm4TaQkrqcz32rPxxLQhySd1D6ZFdB0zvCSF1cv+x\nC98omdQTKlKY3PVdFhpVFGkhSNc29Pabb8l2Vv6EygZiZxWM9ISQOoX7qepGfOb0JjZCbUGpbN2o\nc0JdWxt/fNdJsvLHdYvTN+OLkVUw0hNC6hgN+uXlZWzduhXDw8MAgMXFRZTLZXR3d2NoaAi1Wk0p\nL4RIvYsl7+aqu35a22SUkr1MbMg+s7Gl0qeyHeoYfPXo+iANE39sfE7K5O2PzTk28T2UHpNjkGE0\n6I8dO4a+vr66s+Pj4yiXy5ie
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 283
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(Summary)\n",
|
||
|
|
"\n",
|
||
|
|
"- we implemented Rule 110 as a recurrent, single-layer neural network with McCulloch-Pitts neurons\n",
|
||
|
|
"- Rule 110 can emulate a tag system\n",
|
||
|
|
"- a tag system can emulate a Turing machine\n",
|
||
|
|
"\n",
|
||
|
|
"Therefore, recurrent single layer neural networks are Turing complete.\n",
|
||
|
|
"\n",
|
||
|
|
"We also could emulate a Turing machine directly."
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"metadata": {}
|
||
|
|
}
|
||
|
|
]
|
||
|
|
}
|