<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Bar Vinograd on Medium]]></title>
        <description><![CDATA[Stories by Bar Vinograd on Medium]]></description>
        <link>https://medium.com/@barvinograd1?source=rss-16b5858e8358------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*4qS1qwOMtmQnTftn.jpg</url>
            <title>Stories by Bar Vinograd on Medium</title>
            <link>https://medium.com/@barvinograd1?source=rss-16b5858e8358------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 00:24:51 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@barvinograd1/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Instance Embedding: Segmentation Without Proposals]]></title>
            <link>https://medium.com/data-science/instance-embedding-instance-segmentation-without-proposals-31946a7c53e1?source=rss-16b5858e8358------2</link>
            <guid isPermaLink="false">https://medium.com/p/31946a7c53e1</guid>
            <category><![CDATA[instance-segmentation]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[computer-vision]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[Bar Vinograd]]></dc:creator>
            <pubDate>Sun, 01 Apr 2018 08:10:41 GMT</pubDate>
            <atom:updated>2018-04-26T13:00:39.660Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/943/1*73E15g6xOD8leNHppZZycw.png" /></figure><p>In this article I will review 3 papers in the field of instance segmentation. They are different from the mainstream proposal-based Faster-RCNN based approach like <a href="https://arxiv.org/abs/1703.06870">Mask-RCNN</a> or <a href="https://arxiv.org/abs/1712.04837">MaskLab</a> and the latest <a href="https://arxiv.org/abs/1803.01534">PANet</a>, achieving state-of-the-art results on multiple datasets (<a href="https://www.cityscapes-dataset.com/">CityScapes</a>, <a href="http://cocodataset.org/">COCO</a>, <a href="https://www.mapillary.com/dataset/vistas">MVD</a>). See tutorial on Mask-RCNN <a href="http://kaiminghe.com/iccv17tutorial/maskrcnn_iccv2017_tutorial_kaiminghe.pdf">here</a>.</p><p>There are three fundamental flaws in a proposal-based instance segmentation architecture. First, two objects may share the same bounding box, or a very similar boxes. In this case, the mask head, has no way of telling which object to pick in the box. This is a serious problem with stringy like object that have low fill rate in their bounding box (e.g. bicycles and chairs). Second, there is nothing in the architecture preventing a pixel to be shared between two instance. Third, the number of instances is limited by the number of proposals processed by the network (usually hundreds).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*hKOJOX99Mxg_O3Yr." /><figcaption>architecture for Mask-RCNN, <a href="https://www.slideshare.net/IldooKim/deep-object-detectors-1-20166">https://www.slideshare.net/IldooKim/deep-object-detectors-1-20166</a></figcaption></figure><p>More over, the architecture is complex and hard to tune and “debug”. In object detection, a precursor to this problem, there are already successes being made to use a simpler, single-stage, architectures e.g. <a href="https://arxiv.org/abs/1708.02002">RetinaNet</a>.</p><p>With instance embedding, each object is assigned a “color” in a n-dimensional space. The network processes the image and produces a dense output, same size as the input image. Each pixel in the output of the network is a point in the embedding space. Pixels that belong to the same object are close in the embedding space while pixels that belong to different objects are distant in the embedding space. Parsing the image embedding space involves some sort of clustering algorithm.</p><h3>Paper 1: Semantic Instance Segmentation with a Discriminative Loss Function</h3><p><a href="https://arxiv.org/find/cs/1/au:+Brabandere_B/0/1/0/all/0/1">Bert De Brabandere</a>, <a href="https://arxiv.org/find/cs/1/au:+Neven_D/0/1/0/all/0/1">Davy Neven</a>, <a href="https://arxiv.org/find/cs/1/au:+Gool_L/0/1/0/all/0/1">Luc Van Gool</a> <a href="https://arxiv.org/abs/1708.02551">https://arxiv.org/abs/1708.02551</a><br><a href="https://github.com/DavyNeven/fastSceneUnderstanding">https://github.com/DavyNeven/fastSceneUnderstanding</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/0*PYT_oRjBL-4tGm0B." /><figcaption>visualizing the contrastive loss.</figcaption></figure><p><strong>The Loss.</strong> This paper uses a contrastive loss function complied from 3 parts:</p><p>(1) A pull force. Penalizing the distance of all elements of the same instance from their mean. That is, taking all pixels of an instance and calculating their mean. The pull force will draw all pixel embeddings of the same instance to the same point. In short, reducing the variance of the embedding per instance.</p><p>(2) A push force. Taking all the center points (in the embedding space, not the spatial center) and pushing them farther apart.</p><p>(3) Regularization. Centers shouldn’t be too far from the origin.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/552/1*n7d5zeLPcxRq_2NpQ1X90g.png" /></figure><p>Alpha and beta are used with the value of 1 and gamma is set to be 0.001. Both deltas are thresholds for the pull and push forces.</p><p><strong>Parsing</strong>. After obtaining the semantic segmentation map (car, dog, computer, …) we subdivide each class mask to instances. This is done by picking a random unassigned point in the semantic mask and iteratively applying the mean-shift algorithm to find the mean point of the instance.</p><p>The first hypothesis for the mean is the embedding of the random pixel which was initially picked. Then a set of points is expanded around that point (in the embedding space) and their mean is then again calculated and the process repeats until the change to the mean is not significant. In my experience, it take no more than 10 iterations for the algorithm to converge. And most of the time 3–4 iterations are enough.</p><p>The radius used to expand the instance mask in embedding space is the same as the pull threshold. Theoretically, if the test error is 0, and the minimum distance between centers is at least twice as large as the pull threshold for the variance component we can use these thresholds to parse the image. All points at a distance of no greater than the pull threshold should belong to the same instance. Since the test error is almost never 0, the mean-shift algorithm is used to find the center of a high density part of the embedding.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FhJg7ik4x95U%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DhJg7ik4x95U&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FhJg7ik4x95U%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="640" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/01b4f4d1ac52dab03039e2d42d8545fd/href">https://medium.com/media/01b4f4d1ac52dab03039e2d42d8545fd/href</a></iframe><p><strong>Source of error</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/442/1*eAgv5h2BhHwWumPP0bzgzQ.png" /></figure><p>These results show where most of the error comes from on the Cityscapes Dataset. if the semantic segmentation is not predicated and the ground truth is rather used, the AP50 results jumps from 40.2 to 58.5. If the actual center is also used and not estimated using mean-shift, the score gains almost another 20 points, reaching to 77.8. Current state of the art results without pretraining on COCO is 57.1 using <a href="https://arxiv.org/abs/1803.01534">PANet</a> (see <a href="https://www.cityscapes-dataset.com/benchmarks/">dashboard</a>). Same as using the semantic segmentation ground truth. We learn that the embedding itself is probably pretty good.</p><h3>Example Embedding</h3><p>Below is an example instance embedding produces by a network trained by, yours truly. It is used to solve the problem presented by the <a href="https://www.kaggle.com/c/data-science-bowl-2018">Data Science Bowl 2018</a>, currently running on Kaggle. The purpose is to find cell nuclii in medical images.</p><p>The top-left image is the original image. Middle-top image is the semantic segmentation (here with only two classes, background and foreground). The rest of the images are the first 7 channels of 64 of embedding space. It is evident from the embedding that the network learned channels that spatially differentiate the nuclei. Example for diagonal or horizontal coding. Some encode the distance from center of the image. However, inside an instance the color is homogeneous. This is giving us some insight to how the network learned to segment instances.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*2U0aA1GvO-m3Rw8Y." /></figure><h3>Paper 2: Semantic Instance Segmentation via Deep Metric Learning</h3><p><a href="https://arxiv.org/find/cs/1/au:+Fathi_A/0/1/0/all/0/1">Alireza Fathi</a>, <a href="https://arxiv.org/find/cs/1/au:+Wojna_Z/0/1/0/all/0/1">Zbigniew Wojna</a>, <a href="https://arxiv.org/find/cs/1/au:+Rathod_V/0/1/0/all/0/1">Vivek Rathod</a>, <a href="https://arxiv.org/find/cs/1/au:+Wang_P/0/1/0/all/0/1">Peng Wang</a>, <a href="https://arxiv.org/find/cs/1/au:+Song_H/0/1/0/all/0/1">Hyun Oh Song</a>, <a href="https://arxiv.org/find/cs/1/au:+Guadarrama_S/0/1/0/all/0/1">Sergio Guadarrama</a>, <a href="https://arxiv.org/find/cs/1/au:+Murphy_K/0/1/0/all/0/1">Kevin P. Murphy</a> <br><a href="https://arxiv.org/abs/1703.10277">https://arxiv.org/abs/1703.10277</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*g9KUrM-IFijKywX-." /><figcaption>Network architecture proposed in Semantic Instance Segmentation via Deep Metric Learning</figcaption></figure><p>The main contribution in this paper is a seediness score which is learned for each pixel. The score tells us if the pixel is a good candidate to expand a mask around. In the previous paper the seed was chosen at random and then the center was refined using the mean-shift algorithm. Here, only one expansion is made.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/225/0*S382qDDi2S8nFUVd." /><figcaption>seedeness score per pixel. taken as the maximum over all classes and bandwidths.</figcaption></figure><p>The paper propose to learn several possible seeds for each pixel. We learn a seed for each radius (in embedding space) and class. So if we have C classes and we learn T bandwidths (radii) we have CxT seed “proposals” per pixel. For each pixel only the proposal with the highest score is considered.</p><p><strong>Embedding Loss. </strong>In this paper, the embedding is penalized for pairs of pixels. We consider pairs that are of the same instance and pairs from different instances.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/349/0*C0JEC4d2sHPRMPIb." /><figcaption>a logistic distance function in embedding space</figcaption></figure><p>The paper uses a modified logistic function that transforms the euclidean distance in embedding space to the [0, 1] domain. Pairs that are close in the embedding space will be assigned a value close to 1 by the function, pairs that are distant will approach 0.</p><p>Naturally, logloss is used as a loss function. Instances sizes may vary so, in order to mitigate this imbalance issue, pairs are weighted with respect to the size of the instance they are a part of.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/378/1*aklQ2hqQpbJ9u-S-p95rzw.png" /><figcaption>logloss over logistic distance between pairs of pixels</figcaption></figure><p><strong>Seediness Loss. </strong>For each pixel, the model learns several seediness scores. One score for each combination of bandwidth (radius in embedding space) and class. Since the seediness score is close but not the same as semantic segmentation, the ground truth for each is determined every time the embedding is evaluated. A mask is expanded around the embedding of a pixel and if the IoU with a ground truth instance exceeds a certain threshold, the pixel is considered as a seed for the class of the instance. The loss will then penalize a low seediness score for this class.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/384/0*26PsDHQzweWbcccn." /><figcaption>seediness loss</figcaption></figure><p>Only 10 or so seeds are evaluated per image in each batch, picked randomly. Several such models are learned, one for each bandwidth. The wider the bandwidth, the larger the object. In a way, the bandwidth that received the highest score, is the model’s way to convey it’s estimation to the instance size (with respect to the distances in the embedding space).</p><p><strong>Training Procedure. </strong>The paper uses ResNet-101 backbone pretrained on the COCO dataset. Training starts with no classification/seediness predication i.e. λ=0 and progresses to 0.2 as the embedding is more stable.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/213/1*25y46E_ezGr94BlNK6yU9A.png" /></figure><p>The backbone is evaluated at different scales (0.25, 0.5, 1, 2) and the concatenated results are fed to the seediness and embedding heads.</p><p><strong>Parsing</strong>. The procedure pretty straight forward since the seeds learned. The paper proposes a procedure to pick the best seed set for an image. It optimizes for a high seediness score on one hand and diversity in the embedding space on the other.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/570/0*1hPGRNNFwr0d5WYG." /></figure><p>Seeds are chosen iteratively, each new seed is chosen to be distant in the embedding space from the previously selected seeds. The first seed selected is the pixel with the highest seediness score in the image. The second one will be the seed that on one hand has a high seediness score and on the other hand is not close in the embedding space. The balance between the two requirements is controlled using the parameter alpha. Alpha is a to be tuned, the range tested for this parameter is between 0.1 and 0.6. Unlike NMS, diversity in embedding space is encouraged, rather than spatial diversity.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/618/0*-ZNb-CVraFaUCFE_." /><figcaption>some results from Semantic Instance Segmentation via Deep Metric Learning</figcaption></figure><h3>Paper 3: Recurrent Pixel Embedding for Instance Grouping</h3><p><a href="https://arxiv.org/find/cs/1/au:+Kong_S/0/1/0/all/0/1">Shu Kong</a>, <a href="https://arxiv.org/find/cs/1/au:+Fowlkes_C/0/1/0/all/0/1">Charless Fowlkes</a><br><a href="https://arxiv.org/abs/1712.08273">https://arxiv.org/abs/1712.08273</a><br><a href="https://github.com/aimerykong/Recurrent-Pixel-Embedding-for-Instance-Grouping">https://github.com/aimerykong/Recurrent-Pixel-Embedding-for-Instance-Grouping</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/690/0*RFwW286zQuYOeCPp." /></figure><p>This paper proposes to have the embedding on a n-sphere and to measure proximity of pixels using the cosine distance. However, the main contribution is this paper is the recurrent grouping model, based on a modified version of the Gaussian Blurring Mean-Shift (GBMS) algorithm.</p><p>GBMS is an iterative algorithm like the simple mean-shift algorithm used to find instance centers in the first paper. In this version, all the pixels are considered to be potential seeds. All pixels are updated at each iteration with respect to the density around them. Moving toward a “center of gravity”, as if the embedding space of the image was a nebula producing planets. The farther points are from each other, the less of the effect they will have on one another. The distance is controlled by the bandwidth of the Gaussian, it’s standard deviation, as is clear from the algorithm below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/536/0*NBDyeIcrSvhvqx42." /></figure><p>For GBMS there are cubic convergence guarantees so eventually we should get very dense, almost point-like, clusters after applying the transform several times. For more on GBMS see <a href="http://www.cs.cmu.edu/~aarti/SMLRG/miguel_slides.pdf">here</a>.</p><p>In order to incorporate the algorithm in the network, it has be expressed using operations on matrices.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/533/0*3z21-wzUPCuRZ9kc." /></figure><p>Simply applying the algorithm described above is does not make sense since the embedding are on a sphere and their proximity is measured using the cosine transform. The affinity matrix, describing the distances between all points is calculated using the following transformation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/220/0*sIDr2K3mkoiqLeNR." /></figure><p>Measuring distances on the sphere, rather than using the L2 norm. In addition, after applying a GBMS step, it is required to normalize the resulting embeddings so they will be on the unit sphere.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*hs7RhCoBikkGdSzw." /></figure><p><strong>Training.</strong> Pairwise pixel loss is used, similarly to the previous paper with a threshold on the distance required from dissimilar pairs (alpha). Each pair is evaluated using a calibrated cosine distance which ranges [0,1] instead of [-1, -1].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/1*slRREbiolW6BFjeNNGGGpw.png" /><figcaption>calibrated cosine distance</figcaption></figure><p>The loss is back-propagated through each application of the recurrent grouping model. Later stages of application will surface only very difficult cases. The authors compare this property to hard negative mining used in the training of Faster-RCNN, for example.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/671/0*optGvm68SkyMuzbW." /><figcaption>loss used in Recurrent Pixel Embedding for Instance Grouping</figcaption></figure><p>The authors are using 0.5 as value for alpha in the paper. Notice that the size of the instance is used to re-balance the loss between small and large instances.</p><p><strong>Parsing.</strong> After several applications of the grouping module, the clusters should be very dense, picking values at random should produce good enough seeds.</p><p>For practical purposes, it makes sense to use only some of the pixels in the GBMS steps since computing the similarity matrix might prove prohibitively expensive. The amount of pixels taken is a speed/accuracy trade-off consideration.</p><h3>Other approaches</h3><p>Instance embedding is not the only alternative to proposal based networks. Here are some papers that use other methods to solve the problem of instance segmentation</p><ul><li><strong>End-to-End Instance Segmentation with Recurrent Attention</strong><br><a href="https://arxiv.org/abs/1605.09410">https://arxiv.org/abs/1605.09410</a></li><li><strong>Deep Watershed Transform for Instance Segmentation</strong><br><a href="https://arxiv.org/abs/1611.08303">https://arxiv.org/abs/1611.08303</a></li><li><strong>Associative Embedding: End-to-End Learning for Joint Detection and Grouping</strong><br><a href="http://ttic.uchicago.edu/~mmaire/papers/pdf/affinity_cnn_cvpr2016.pdf">http://ttic.uchicago.edu/~mmaire/papers/pdf/affinity_cnn_cvpr2016.pdf</a></li><li><strong>SGN: Sequential Grouping Networks for Instance Segmentation </strong><br><a href="https://www.cs.toronto.edu/~urtasun/publications/liu_etal_iccv17.pdf">https://www.cs.toronto.edu/~urtasun/publications/liu_etal_iccv17.pdf</a></li></ul><h3>Summary</h3><p>Compared to proposal based solutions, the results from these papers are not competitive. We have reviewed 3 papers with different solution approaches to the loss and the parsing.</p><p>(1) <strong>Semantic Instance Segmentation with a Discriminative Loss Function</strong><br>Used a non-pairwise loss function. Producing far richer gradients using all the pixels in the image.</p><p>(2) <strong>Semantic Instance Segmentation via Deep Metric Learning</strong><br>Introduces a seediness model, helping us to classify and pick the best seeds at the same time, optimizing for speed.</p><p>(3) <strong>Recurrent Pixel Embedding for Instance Grouping</strong><br>GBMS, a variant of mean-shift, was used inside the network in both training and parsing. Creates very dense clusters.</p><p>These approaches could probably be combined and refined to produce far better results. They are simpler and possibly faster than proposal based approaches while avoiding the fundamental flaws mentioned in the intro to this paper at the same time.</p><p><strong>Contact:</strong> me@barvinograd.com</p><p><strong>Slides: </strong><a href="https://goo.gl/iTC9aS">https://goo.gl/iTC9aS</a></p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FFB_SZIKyX50%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DFB_SZIKyX50&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FFB_SZIKyX50%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/d9925a7d749c0d54d59c4d9a91864af4/href">https://medium.com/media/d9925a7d749c0d54d59c4d9a91864af4/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=31946a7c53e1" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/instance-embedding-instance-segmentation-without-proposals-31946a7c53e1">Instance Embedding: Segmentation Without Proposals</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Cyclic Tag System: 1 Line of Turing-Complete Code]]></title>
            <link>https://medium.com/@barvinograd1/cyclic-tag-system-1-line-of-turing-complete-code-cebe8e18658f?source=rss-16b5858e8358------2</link>
            <guid isPermaLink="false">https://medium.com/p/cebe8e18658f</guid>
            <category><![CDATA[cellular-automata]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[church-turing-hypothesis]]></category>
            <category><![CDATA[computer-science]]></category>
            <dc:creator><![CDATA[Bar Vinograd]]></dc:creator>
            <pubDate>Sat, 24 Feb 2018 15:31:46 GMT</pubDate>
            <atom:updated>2018-02-24T15:32:46.147Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*O_rqFu_FBdQ1R0kLZn8JOA.png" /></figure><p>The following line of python code is able to simulate a Universal Turing Machine:</p><pre>while len(word) &gt; S : pIndex, word = (pIndex + 1) % len(C), word[1:] + C[pIndex] if (word[0] == “1”) else word[1:]</pre><p>It is 114 characters long and can probably reduced further using some clever python tricks. It implements one of the most extraordinarily simple Turing-Complete models: a Cyclic Tag System or CTS. The CTS was first introduced by Mathew Cook in 2004 when he published his <a href="http://www.complex-systems.com/pdf/15-1-1.pdf">paper</a> on the universality of <a href="https://en.wikipedia.org/wiki/Elementary_cellular_automaton">Elementary Cellular Automata</a> and specifically <a href="https://en.wikipedia.org/wiki/Rule_110">Rule 110</a>. This rule, simple on its own right but out of scope for this post, was long suspected to be able to simulate a <a href="https://en.wikipedia.org/wiki/Universal_Turing_machine">Universal Turing Machine</a> (and thus <a href="https://en.wikipedia.org/wiki/Turing_completeness">Turing-Complete</a>). It was Cook who proved this conjecture while working for Steven Wolfram at Wolfram Research.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*NmaZ7NESgZ_o5YrNNLUa2w.png" /><figcaption>Rule 110 in action (from Cook’s paper)</figcaption></figure><p>For those willing to read the whole thing, I have included a bonus : how the Collatz Conjecture can be simulated using CTS.</p><h3>How does a Cyclic Tag System work?</h3><p>If you think of a cyclic tag system as your CPU then you would have your code as an array of binary words, lets call it <em>C = α₁α₂…αₚ₋₁ </em>(same in code above). By binary words I mean a string of <em>0</em>’s and <em>1</em>’s. This is your Assembly code, machine language if you like. The <em>αₖ</em>’s are called appendants. Your data, the input parameter is a binary word, lets call it <em>W = w₀w₁…wₙ</em> (it is the variable ‘word’ in the code above). <em>C</em> never changes during execution, but we do keep track of which part of the program we are executing with a pointer, lets call it <em>k</em> (pIndex in code above). The executer of our program cycles through the program in a never ending manner. Execution halts when the word <em>W</em>, which is being manipulated during execution (bear with me) is shorter or equal than <em>S</em>, some integer. Each execution step consists of the following actions:</p><pre>while |w| &lt; S<br>   if w₀ = 1<br>     then W = w₁…wₙαₖ <em><br>     else </em>W = w₁…wₙ<br>   k = (k + 1) mod p</pre><p><strong>Example 1</strong></p><pre>C = [0, 1] W = 001, S = 1<br>Step #  k  W<br>1       0  001<br>2       1  01<br>3       0  1</pre><p>The execution halts when the length of the word is 1.</p><p><strong>Example 2</strong></p><pre>C = [10, 101], W = 001, S = 1<br>Step #  k  W<br>1       0  10<br>2       1  010<br>3       0  10</pre><p>Here, in every odd state the first appendant is used and in every even state the second is ignored and we have an endless loop which never halts.</p><h3>Turing Completeness</h3><p>In order to prove that something is Turing-Complete one should show that it can emulate a Universal Turing Machine (UTM). If it can, it can do anything a UTM does and thus universal, this is the <a href="https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis">Church-Turing Thesis</a>. Intuitively it will be as general purpose as your Desktop, iPhone, and favorite programming language. Now, you can directly show that something can emulate UTM, but it is sometimes more convenient to show that a model can emulate another Turing-Complete model. Computational capacity is a transitive relation. If A emulate a UTM and B emulates A so B emulates a UTM.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*F_5_b5FlPbdBLWXqNSj-5A.png" /></figure><p>Cook showed that Rule 110 can emulate an UTM by going through 2 steps. He first showed that a construction by Emil Post called a 2-tag system can be emulated by a CTS and then he showed that Rule 110 can emulate a CTS; thus proving the claim. There is actually another proof of CTS universality published by <a href="http://www.cs.may.ie/~tnaughton/abc/download/dw15.pdf">Neary and Woods in 2006,</a> 2 years after Cook’s first proof. They use a novel model, a Clockwise Turing Machine which is Turing-Complete instead of a 2-tag system. Cook’s original proof has an exponential time scale up. Using a Clockwise Turing Machine only a polynomial scale up was achieved which is quite remarkable. The proof by Neary and Woods is quite complex and the eager reader is referred to their paper. I will review Cook’s very intuitive and short proof.</p><h3>2-Tag System</h3><p>A 2-tag system has an alphabet <em>A</em> and a set of Production Rules <em>P : A→A*</em>. The computation is very similar to the circular tag system. We have an initial word <em>W = w₀w₁…wₙ</em>. At each step we check if the word is 2 symbols or more in length. If it is, we delete 2 letters from the left side of the word, <em>w₀w₁,</em> and append <em>P(w₀)</em> to the right side of the word, otherwise we halt.</p><p><strong>Example 1</strong></p><pre>A = {a, b}, P(a) = bb, P(b) = ε, W = aaa<br>Step #   W <br>0        aaa<br>1        abb<br>2        bbb<br>3        b</pre><p><em>ε</em> being the empty word</p><p><strong>Example 2</strong></p><pre>A = {a, b}, P(a) = ’ab’, P(b) = ε, W = <br>Step #   W <br>0        ab<br>1        ab<br>…</pre><p>just like in the second example of CTS, the execution here never halts and the state of the system always cycles.</p><p>Python code for the first example:</p><pre>P = {&#39;a&#39;: &#39;bb&#39;, &#39;b&#39;: &#39;&#39;}<br>word = &#39;aaa&#39;<br>S = 1<br>while len(word) &gt; S: word = word[2:] + P[word[0]]</pre><p>the implemetation here is even simpler than the CTS’.</p><h3>Cyclic Tag System Can Emulate 2-Tag System</h3><p>Suppose we have a 2-tag system with <em>A =a₀a₁…a</em>ₖ we can encode each character in a binary manner in following way T(<em>a</em>ₙ)<em>→</em>0..010..0 where the <em>1 </em>is in position <em>n</em>. The program C =<em>α₁α₂…αₚ </em>will be constructed in the following manner: If P(aₙ) = aₙ₁aₙ₂…aₙₙ for each aₙ we set <em>a</em>ₙ<em>₋₁</em>=T(aₙ₁)T(aₙ₂)…T(aₙₙ). We would also add <em>k</em> empty appendants to <em>C</em> and overall we have <em>|C| = 2k</em></p><p>The proof: First, notice that each time the CTS starts reading a sequence of <em>k</em> characters from the word it will be at the beginning of <em>C</em> or half-way through it, at the beginning of the <em>k</em> additional empty appendants we added to <em>C</em>.</p><p>If pIndex=0thus points to the beginning of <em>C </em>it will encounter a single <em>1</em> while going through the word when at position <em>n-1</em> which corresponds to the iᵗʰ symbol of the 2-tag system and appends T(aₙ) to the word. The CTS will go through 0’s until it reaches position pIndex=k-1.</p><p>If pIndex=k-1 it will delete <em>k</em> letters from the word and append empty strings to the word and in essence ignore the character represented by those <em>k</em> binary symbols in the word. It will then cycle to the beginning of <em>C </em>and we find ourselves in the previous paragraph.</p><p>If we set <em>S = k, </em>it is easy now to see that the constructed CTS emulates the 2-tag system perfectly.</p><p>The following python code is an implementation of the conversion above with the parameters from the 2-tag system and input in example 1.</p><pre># conversion <br>def TwoTagSymbolToBinaryWord(A, s):<br> idx = A.index(s)<br> return (&#39;0&#39; * idx) + &#39;1&#39; + &#39;0&#39; * (len(A) — idx — 1)<br> <br>def TwoTagWordToBinaryWord(A, w):<br> t = &#39;&#39;<br> for i in xrange(len(w)):<br> t += TwoTagSymbolToBinaryWord(A, w[i])<br> return t<br> <br>def TwoTagToCTS(A, P):<br> C = []<br> <br> for i in xrange(len(A)):<br> C.append(&#39;&#39;)<br> C[i] += TwoTagWordToBinaryWord(A, P[A[i]])<br> <br> for i in xrange(len(A)):<br> C.append(&#39;&#39;)<br> <br> return C, len(A)</pre><pre># 2-Tag System <br>A = [&#39;a&#39;, &#39;b&#39;]<br>P = {&#39;a&#39;: &#39;bb&#39;, &#39;b&#39;: &#39;&#39;}</pre><pre># input for 2-tag<br>word = &#39;aaa&#39;</pre><pre># convert <br>C, S = TwoTagToCTS(A, P)<br>wordCTS = TwoTagWordToBinaryWord(A, word)<br>print &quot;S: &quot; + str(S)<br>print &quot;C: &quot; + str(C)<br>print &quot;Input: &quot; + wordCTS<br>print &quot;step #\tpIndex\tword&quot;</pre><pre># run and print CTS<br>step = 1<br>pIndex = 0</pre><pre># CTS Step<br>def DoCTSStep(word, C, pIndex):<br> w0 = word[0]<br> word = word[1:]<br> if (w0 == &#39;1&#39;):<br> word = word + C[pIndex]<br> pIndex = (pIndex + 1) % len(C)<br> return word, pIndex</pre><pre>print str(step) + &quot;\t&quot; + str(pIndex) + &quot;\t&quot; + wordCTS</pre><pre>while len(wordCTS) &gt; S:<br> wordCTS, pIndex = DoCTSStep(wordCTS, C, pIndex)<br> step+=1<br> print str(step) + &quot;\t&quot; + str(pIndex) + &quot;\t&quot; + wordCTS</pre><p>The code outputs the following (with comments)</p><pre>S: 2<br>C: [&#39;0101&#39;, &#39;&#39;, &#39;&#39;, &#39;&#39;]<br>Input: 101010<br>step # pIndex word<br>1      0      101010          =aaa<br>2      1      010100101 <br>3      2      10100101        deletes the second symbol<br>4      3      0100101 <br>5      0      100101          =abb<br>6      1      001010101 <br>7      2      01010101        deletes the second symbol<br>8      3      1010101<br>9      0      010101          =bbb<br>10     1      10101<br>11     2      0101            deletes the second symbol<br>12     3      101 <br>13     0      01 =b</pre><p>As expected the code halts and simulates the 2-tag system run.</p><h3>2-Tag System Can Emulate A Turing Machine</h3><p>There are actually at least 3 different proofs for the universality of tag systems. The first was provided by <a href="http://nkscience.org/prizes/tm23/images/Minsky.pdf">Minsky in 1961</a> and the <a href="https://dspace.mit.edu/bitstream/handle/1721.1/6107/AIM-052.pdf?sequence=2">second</a> by Cooke and Minsky 2 years later, in 1963. The third proof was provided by Cook in his paper on the universality of Rule 110 from 2004.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/806/1*W8TKzZ2su9WgGlQj0DqPRg.png" /><figcaption>from Minsky’s paper</figcaption></figure><p>The two later proofs are the simplest IMHO. The reader may follow both in the original papers, they are not long. They are too technical, however inspiring, for this scope.</p><h3>Bonus: The Collatz Conjecture with 2-Tag System</h3><p>Using the correct configuration, Liesbeth De Mol, showed in her paper from 2008, how the <a href="https://en.wikipedia.org/wiki/Collatz_conjecture">Collatz Conjecture</a> can be reproduced in a tag system. A reminder: the conjecture asserts that the following sequence will always terminate with <em>1</em>. If <em>n</em> is odd, the next element in the sequence is <em>3n+1</em>. If even the next element is <em>n/2</em>. It has been long standing since 1937 when first proposed by Lothar Collatz.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/311/1*OlyV29m2g6ZpWu0SQcbbnQ.png" /><figcaption>XKCD on the Collatz Conjecture</figcaption></figure><p>We encode a natural number with <em>n</em> a’s. ‘<em>b’</em>, and ‘<em>c</em>’ will also be included in the alphabet. The production rules are as follows: <em>P(a) = bc</em>, <em>P(b) = a</em>, <em>P(c) = aaa</em>. It should terminate with ‘a’ or ‘100’ in CTS jargon. Voila!</p><pre>A = [&#39;a&#39;, &#39;b&#39;, &#39;c&#39;]<br>P = {&#39;a&#39;: &#39;bc&#39;, &#39;b&#39;: &#39;a&#39;, &#39;c&#39;: &#39;aaa&#39;}</pre><p>outputs</p><pre>S: 3<br>C: [‘010001’, ‘100’, ‘100100100’, ‘’, ‘’, ‘’]<br>Input: 100100100<br>step # pIndex word<br>1      0      100100100<br>2      1      00100100010001<br>3      2      0100100010001<br>4      3      100100010001<br>5      4      00100010001<br>6      5      0100010001<br>7      0      100010001<br>8      1      00010001010001<br>9      2      0010001010001<br>10     3      010001010001<br>11     4      10001010001<br>12     5      0001010001<br>13     0      001010001<br>14     1      01010001<br>15     2      1010001<br>16     3      010001100100100<br>17     4      10001100100100<br>18     5      0001100100100<br>19     0      001100100100<br>20     1      01100100100<br>21     2      1100100100<br>22     3      100100100100100100<br>23     4      00100100100100100<br>24     5      0100100100100100<br>25     0      100100100100100<br>26     1      00100100100100010001<br>27     2      0100100100100010001<br>28     3      100100100100010001<br>29     4      00100100100010001<br>30     5      0100100100010001<br>31     0      100100100010001<br>32     1      00100100010001010001<br>33     2      0100100010001010001<br>34     3      100100010001010001<br>35     4      00100010001010001<br>36     5      0100010001010001<br>37     0      100010001010001<br>38     1      00010001010001010001<br>39     2      0010001010001010001<br>40     3      010001010001010001<br>41     4      10001010001010001<br>42     5      0001010001010001<br>43     0      001010001010001<br>44     1      01010001010001<br>45     2      1010001010001<br>46     3      010001010001100100100<br>47     4      10001010001100100100<br>48     5      0001010001100100100<br>49     0      001010001100100100<br>50     1      01010001100100100<br>51     2      1010001100100100<br>52     3      010001100100100100100100<br>53     4      10001100100100100100100<br>54     5      0001100100100100100100<br>55     0      001100100100100100100<br>56     1      01100100100100100100<br>57     2      1100100100100100100<br>58     3      100100100100100100100100100<br>59     4      00100100100100100100100100<br>60     5      0100100100100100100100100<br>61     0      100100100100100100100100<br>62     1      00100100100100100100100010001<br>63     2      0100100100100100100100010001<br>64     3      100100100100100100100010001<br>65     4      00100100100100100100010001<br>66     5      0100100100100100100010001<br>67     0      100100100100100100010001<br>68     1      00100100100100100010001010001<br>69     2      0100100100100100010001010001<br>70     3      100100100100100010001010001<br>71     4      00100100100100010001010001<br>72     5      0100100100100010001010001<br>73     0      100100100100010001010001<br>74     1      00100100100010001010001010001<br>75     2      0100100100010001010001010001<br>76     3      100100100010001010001010001<br>77     4      00100100010001010001010001<br>78     5      0100100010001010001010001<br>79     0      100100010001010001010001<br>80     1      00100010001010001010001010001<br>81     2      0100010001010001010001010001<br>82     3      100010001010001010001010001<br>83     4      00010001010001010001010001<br>84     5      0010001010001010001010001<br>85     0      010001010001010001010001<br>86     1      10001010001010001010001<br>87     2      0001010001010001010001100<br>88     3      001010001010001010001100<br>89     4      01010001010001010001100<br>90     5      1010001010001010001100<br>91     0      010001010001010001100<br>92     1      10001010001010001100<br>93     2      0001010001010001100100<br>94     3      001010001010001100100<br>95     4      01010001010001100100<br>96     5      1010001010001100100<br>97     0      010001010001100100<br>98     1      10001010001100100<br>99     2      0001010001100100100<br>100    3      01010001100100100<br>101    4      01010001100100100<br>102    5      1010001100100100<br>103    0      010001100100100<br>104    1      10001100100100<br>105    2      0001100100100100<br>106    3      001100100100100<br>107    4      01100100100100<br>108    5      1100100100100<br>109    0      100100100100<br>110    1      00100100100010001<br>111    2      0100100100010001<br>112    3      100100100010001<br>113    4      00100100010001<br>114    5      0100100010001<br>115    0      100100010001<br>116    1      00100010001010001<br>117    2      0100010001010001<br>118    3      100010001010001<br>119    4      00010001010001<br>120    5      0010001010001<br>121    0      010001010001<br>122    1      10001010001<br>123    2      0001010001100<br>124    3      001010001100<br>125    4      01010001100<br>126    5      1010001100<br>127    0      010001100<br>128    1      10001100<br>129    2      0001100100<br>130    3      001100100<br>131    4      01100100<br>132    5      1100100<br>133    0      100100<br>134    1      00100010001<br>135    2      0100010001<br>136    3      100010001<br>137    4      00010001<br>138    5      0010001<br>139    0      010001<br>140    1      10001<br>141    2      0001100<br>142    3      001100<br>143    4      01100<br>144    5      1100<br>145    0      100</pre><p><strong>References</strong></p><p>M. Minsky, <a href="http://nkscience.org/prizes/tm23/images/Minsky.pdf">“Recursive Unsolvability of Post’s Problem of ‘Tag’ and Other Topics of Turing Machines”</a>, 74, no. 3, pp. 437–455; November 1961.</p><p>J. Cooke and M. Minksy, “<a href="https://dspace.mit.edu/bitstream/handle/1721.1/6107/AIM-052.pdf?sequence=2">Universality of TAG Systems with P=2</a>”, AI Memos 52, MIT, MA; 1963.</p><p>M. Cook, “<a href="http://www.complex-systems.com/pdf/15-1-1.pdf">Universality in Elementary Cellular Automata</a>”, Complex Systems, vol 15 pp. 1–40; 2004.</p><p>T. Neary, D. Woods, “<a href="http://www.cs.may.ie/~tnaughton/abc/download/dw15.pdf">P-completeness of cellular automaton Rule 110</a>”, Proceesings of ICALP 2006, Lecture Notes in Computer Science, pp.132–143, vol 4051, Springer, Berlin; 2006.</p><p>L. De Mol, “<a href="https://biblio.ugent.be/publication/436211/file/6812232.pdf">Tag Systems and Collatz-Like Functions</a>”, Theoretical Computer Science, vol. 390, issue 1, pp.92–101, January 2008.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=cebe8e18658f" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>