Mercurial > repo
changeset 10279:429f3ab1a941
<oerjan> rm minsk
| author | HackBot |
|---|---|
| date | Thu, 16 Feb 2017 01:06:03 +0000 |
| parents | b1dc3ef300c2 |
| children | bae4827d5de8 |
| files | minsk |
| diffstat | 1 files changed, 0 insertions(+), 360 deletions(-) [+] |
line wrap: on
line diff
--- a/minsk Thu Feb 16 01:05:47 2017 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,360 +0,0 @@ -<!DOCTYPE html> -<html lang="en" dir="ltr" class="client-nojs"> -<head> -<meta charset="UTF-8"/> -<title>The Amnesiac From Minsk - Esolang</title> -<script>document.documentElement.className = document.documentElement.className.replace( /(^|\s)client-nojs(\s|$)/, "$1client-js$2" );</script> -<script>(window.RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"The_Amnesiac_From_Minsk","wgTitle":"The Amnesiac From Minsk","wgCurRevisionId":45748,"wgRevisionId":45748,"wgArticleId":10083,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Languages","Turing complete","Output only","Unimplemented","Cell-based","Low-level","2015"],"wgBreakFrames":false,"wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy","wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgMonthNamesShort":["","Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"],"wgRelevantPageName":"The_Amnesiac_From_Minsk","wgRelevantArticleId":10083,"wgRequestId":"c87139c8cdc92ae552b0a067","wgIsProbablyEditable":false,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgWikiEditorEnabledModules":{"toolbar":true,"dialogs":true,"preview":false,"publish":false}});mw.loader.implement("user.options",function($,jQuery,require,module){mw.user.options.set({"variant":"en"});});mw.loader.implement("user.tokens",function ( $, jQuery, require, module ) { -mw.user.tokens.set({"editToken":"+\\","patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"});/*@nomin*/; - -});mw.loader.load(["mediawiki.page.startup","skins.vector.js"]);});</script> -<link rel="stylesheet" href="/w/load.php?debug=false&lang=en&modules=mediawiki.legacy.commonPrint%2Cshared%7Cmediawiki.sectionAnchor%7Cmediawiki.skinning.interface%7Cskins.vector.styles&only=styles&skin=vector"/> -<meta name="ResourceLoaderDynamicStyles" content=""/> -<link rel="stylesheet" href="/w/load.php?debug=false&lang=en&modules=site&only=styles&skin=vector"/> -<script async="" src="/w/load.php?debug=false&lang=en&modules=startup&only=scripts&skin=vector"></script> -<meta name="generator" content="MediaWiki 1.27.1"/> -<link rel="shortcut icon" href="/favicon.ico"/> -<link rel="search" type="application/opensearchdescription+xml" href="/w/opensearch_desc.php" title="Esolang (en)"/> -<link rel="EditURI" type="application/rsd+xml" href="//esolangs.org/w/api.php?action=rsd"/> -<link rel="copyright" href="/wiki/Esolang:Copyrights"/> -<link rel="alternate" type="application/atom+xml" title="Esolang Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"/> -</head> -<body class="mediawiki ltr sitedir-ltr ns-0 ns-subject page-The_Amnesiac_From_Minsk rootpage-The_Amnesiac_From_Minsk skin-vector action-view"> - <div id="mw-page-base" class="noprint"></div> - <div id="mw-head-base" class="noprint"></div> - <div id="content" class="mw-body" role="main"> - <a id="top"></a> - - <div class="mw-indicators"> -</div> - <h1 id="firstHeading" class="firstHeading" lang="en">The Amnesiac From Minsk</h1> - <div id="bodyContent" class="mw-body-content"> - <div id="siteSub">From Esolang</div> - <div id="contentSub"></div> - <div id="jump-to-nav" class="mw-jump"> - Jump to: <a href="#mw-head">navigation</a>, <a href="#p-search">search</a> - </div> - <div id="mw-content-text" lang="en" dir="ltr" class="mw-content-ltr"><p><b>The Amnesiac From Minsk</b> is a series of <a href="/wiki/Esoteric_programming_language" title="Esoteric programming language">esoteric programming languages</a> designed by <a href="/wiki/User:Ais523" title="User:Ais523">User:ais523</a> towards the end of <a href="/wiki/Category:2015" title="Category:2015">2015</a>. They are arranged as a sequence of "difficulty levels"; higher-level languages are intended to be harder to program in (and lower-level languages can be seen as <a href="/wiki/Wimpmode" title="Wimpmode">wimpmodes</a> for the higher-level languages). <a href="/wiki/Minsky_machine" title="Minsky machine">Minsky machines</a> can be seen as a "level 0", or a wimpmode for the language as a whole, as they have a strict superset of its functionality. -</p><p>In addition to the obvious <a href="/wiki/Minsky_machine" title="Minsky machine">Minsky machines</a>, inspirations for the language include <a href="/wiki/StackFlow" title="StackFlow">StackFlow</a> and <a href="/wiki/Unassignable" title="Unassignable">:≠</a>. It's also less directly inspired by <a href="/wiki/Three_Star_Programmer" title="Three Star Programmer">Three Star Programmer</a> and <a href="/wiki/MiniMAX" title="MiniMAX">MiniMAX</a>, via <a href="/wiki/Last_ReSort" title="Last ReSort">Last ReSort</a>. -</p> -<div id="toc" class="toc"><div id="toctitle"><h2>Contents</h2></div> -<ul> -<li class="toclevel-1 tocsection-1"><a href="#The_Amnesiac_From_Minsk.2C_level_1"><span class="tocnumber">1</span> <span class="toctext">The Amnesiac From Minsk, level 1</span></a> -<ul> -<li class="toclevel-2 tocsection-2"><a href="#Semantics"><span class="tocnumber">1.1</span> <span class="toctext">Semantics</span></a></li> -<li class="toclevel-2 tocsection-3"><a href="#Syntax"><span class="tocnumber">1.2</span> <span class="toctext">Syntax</span></a></li> -<li class="toclevel-2 tocsection-4"><a href="#Implementation_in_and_of_other_languages"><span class="tocnumber">1.3</span> <span class="toctext">Implementation in and of other languages</span></a></li> -</ul> -</li> -<li class="toclevel-1 tocsection-5"><a href="#The_Amnesiac_From_Minsk.2C_level_2"><span class="tocnumber">2</span> <span class="toctext">The Amnesiac From Minsk, level 2</span></a> -<ul> -<li class="toclevel-2 tocsection-6"><a href="#Semantics_2"><span class="tocnumber">2.1</span> <span class="toctext">Semantics</span></a></li> -<li class="toclevel-2 tocsection-7"><a href="#Syntax_2"><span class="tocnumber">2.2</span> <span class="toctext">Syntax</span></a></li> -<li class="toclevel-2 tocsection-8"><a href="#Implementing_level_1_in_level_2"><span class="tocnumber">2.3</span> <span class="toctext">Implementing level 1 in level 2</span></a></li> -<li class="toclevel-2 tocsection-9"><a href="#Implementing_level_2_in_level_1"><span class="tocnumber">2.4</span> <span class="toctext">Implementing level 2 in level 1</span></a></li> -</ul> -</li> -<li class="toclevel-1 tocsection-10"><a href="#The_Amnesiac_From_Minsk.2C_level_3"><span class="tocnumber">3</span> <span class="toctext">The Amnesiac From Minsk, level 3</span></a> -<ul> -<li class="toclevel-2 tocsection-11"><a href="#Semantics_3"><span class="tocnumber">3.1</span> <span class="toctext">Semantics</span></a></li> -<li class="toclevel-2 tocsection-12"><a href="#Syntax_3"><span class="tocnumber">3.2</span> <span class="toctext">Syntax</span></a></li> -<li class="toclevel-2 tocsection-13"><a href="#Implementing_level_3_in_level_2"><span class="tocnumber">3.3</span> <span class="toctext">Implementing level 3 in level 2</span></a></li> -</ul> -</li> -<li class="toclevel-1 tocsection-14"><a href="#The_Amnesiac_From_Minsk.2C_level_4"><span class="tocnumber">4</span> <span class="toctext">The Amnesiac From Minsk, level 4</span></a> -<ul> -<li class="toclevel-2 tocsection-15"><a href="#Semantics_4"><span class="tocnumber">4.1</span> <span class="toctext">Semantics</span></a></li> -<li class="toclevel-2 tocsection-16"><a href="#Syntax_4"><span class="tocnumber">4.2</span> <span class="toctext">Syntax</span></a></li> -<li class="toclevel-2 tocsection-17"><a href="#Implementing_level_4_in_level_3"><span class="tocnumber">4.3</span> <span class="toctext">Implementing level 4 in level 3</span></a></li> -<li class="toclevel-2 tocsection-18"><a href="#Implementation_in_Last_ReSort"><span class="tocnumber">4.4</span> <span class="toctext">Implementation in Last ReSort</span></a></li> -</ul> -</li> -<li class="toclevel-1 tocsection-19"><a href="#See_also"><span class="tocnumber">5</span> <span class="toctext">See also</span></a></li> -</ul> -</div> - -<h2><span class="mw-headline" id="The_Amnesiac_From_Minsk.2C_level_1">The Amnesiac From Minsk, level 1</span></h2> -<h3><span class="mw-headline" id="Semantics">Semantics</span></h3> -<p>At level 1, a The Amnesiac From Minsk program consists of a set of counters, each of which is initialized to a value specified in the program. Each counter can hold an unbounded positive integer (i.e. 0 is not a valid value, so a counter will fail to decrement from 1). The other thing that the program specifies is a list of triggers for each counter: one that runs when the counter is incremented, one which runs when the counter is decremented, and one which runs when an attempt is made to decrement the counter, but which fails because the counter's value is 1. -</p><p>The triggers work in a very similar way to in :≠; when the counter is changed, the corresponding trigger will run immediately afterwards. Unlike in :≠, recursion is allowed, i.e. it's legal for a trigger on a counter to start a cascading chain of triggers that results in another change to that same counter. However, again unlike in :≠, the triggers are tail calls (and thus none of the usual state for tracking recursion is required to implement The Amnesiac From Minsk); the trigger does not return after it runs (or at any other time). Given that every possible change to a counter (and thus everything that you can do in the language) will trigger some trigger or other, this means that there's no point in the code for a trigger containing more than one command, as the first command will never return. (These rules are the same as those used for <code>pop</code> commands in StackFlow.) -</p><p>The program halts if a counter is incremented, and the trigger for that increment causes the same counter to be incremented again. (At this point, it is clear that the program is incapable of making further progress.) Likewise, it halts if a counter fails to decrement from 1, and the trigger for that decrement causes an attempt to be made to decrement that same counter again. The implementation starts by incrementing the first counter, and allowing the program to run its course via triggers from there. -</p><p>As an extension, if a program contains precisely two counters that are not decremented by any trigger, incrementing the one that appears earlier in the program will write a 0 bit to standard output, and incrementing the one that appears later in the program will write a 1 bit to standard output. In the common case where implementations write bits an octet at a time, they should write bits that appear earlier at the more significant end of the byte. -</p> -<h3><span class="mw-headline" id="Syntax">Syntax</span></h3> -<p>Syntactically, the language looks like this: -</p> -<pre>L1 + = - -0: +1; +2; -1; @5 -1: -0; -2; -1; @9 This is a comment. -2: +0; +1; -0; @12 -</pre> -<p>Horizontal whitespace is insignificant anywhere, except that it's disallowed in the middle of a literal integer (although programmers are encouraged to make the columns line up); vertical whitespace is significant. The first line must consist of <code>L1+=-</code>, typically with whitespace added. Each subsequent row line start with a nonnegative integer (the counter number), in sequence starting at 0 and ascending from there. This is followed by the triggers for increment, failed decrement, successful decrement, separated by semicolons; then a semicolon, <code>@</code>, and the initial value for the counter. Anything beyond that is a comment, and should be ignored by implementations. The triggers themselves are expressed as <code>+</code> or <code>-</code> (for increment and for decrement attempt, respectively), followed by the number of the counter to affect. -</p> -<h3><span class="mw-headline" id="Implementation_in_and_of_other_languages">Implementation in and of other languages</span></h3> -<p>A level 1 The Amnesiac From Minsk program is clearly a special case of a Minsky machine (specifically, one in which the program does not have to remember why it tried to increment or decrement a given counter, because all the information is provided with knowledge of what it's currently doing, thus "amnesiac"). -</p><p>Slightly less obviously, but nonetheless with a pretty direct construction, you can compile any level 1 The Amnesiac From Minsk program into StackFlow via representing a counter as a stack with one distinguished symbol at the bottom (that re-pushes itself upon an attempt to pop it) and a different symbol for the other elements of the stack. The "successful decrement" and "failed decrement" triggers have exact analogues in StackFlow (the rules for the "not bottom of stack" and "bottom of stack" symbols for the stack that corresponds to the counter). The "increment" trigger does not directly have an analogue, but because a StackFlow rule can contain multiple <code>push</code> commands, it is possible to simply inline the trigger into every rule that increments the counter corresponding to the stack. -</p><p>Going the other way, The Amnesiac From Minsk can be proved <a href="/wiki/Turing_complete" title="Turing complete" class="mw-redirect">Turing complete</a> at level 1 via implementing Minsky machines in it. The construction works like this: we treat the Minsky machine as a set of counters, plus a state machine that remembers what the system is currently doing. For each state of the state machine, we have a counter that is normally 1, but is 2 while that state is executing. These are connected in chains via failed-decrement triggers; thus attempting to decrement the first counter in a chain will set every counter in the chain to 1 and run the successful-decrement trigger for the current state (if that state is in the chain). -</p><p>This gives a way to increment counters without losing state, using an "increment chain" for all states that do an increment: you increment the counter for the state, have its increment trigger increment the data counter you wanted to increment, have its increment trigger attempt to decrement the first counter in the increment chain, and have the successful-decrement trigger increment the counter for the next state, and so on. It can be seen by inspection that each trigger in the chian is only used for one purpose, meaning that we have no clashes and thus arbitrary increment behaviour will work. -</p><p>For decrements, things are rather more complex; we can't use the same construction directly because a decrement has two possible results. Instead, we have two chains: "successful decrement" (which contains one element per decrementing state), and "failed decrement" (which also contains one element per decrementing state). Additionally, we have two separate counters, "success control" and "failure control", for each decrementing state. As with the implementation of increments, these are all 1 except when a decrement is in progress. You start a decrement via incrementing the "succesful decrement" element for the current state, which (via its increment trigger) increments the "failed decrement" element for the current state, which decrements the data counter in question. Its triggers then attempt to decrement the first element of either the "successful decrement" or "failed decrement" chain, depending on the success or failure of the decrement. -</p><p>The failed-decrement triggers for these two chains are used to maintain the chain behaviour. The successful-decrement triggers for the "successful decrement" and "failed decrement" chains attempt to decrement the "failure control" or "success control" counter respectively for the state in question. Each of these counters will increment the other on a failed decrement, attempt to decrement the first element of the "succesful decrement" or "failed decrement" chain respectively on an increment, and move onto the next state (via incrementing an appropriate chain element to start its increment or decrement) on successful decrement. -</p><p>Here's an example to show how this works, using a successful decrement in the third state in the chain: -</p> -<pre>s.dec chain f.dec chain s.control f.control -11111...111 11111...111 1 1 Before starting the decrement -11211...111 11111...111 1 1 Decrement starts from outside -11211...111 11211...111 1 1 After the first trigger ---- Data counter decremented here, and decrements the s.dec chain --- -11111...111 11211...111 1 1 f.control fails to decrement -11111...111 11211...111 2 1 so it increments s.control -11111...111 11111...111 2 1 which decrements f.dec chain -11111...111 11111...111 1 1 s.control decrement succeeds -</pre> -<p>and now we're back where we started, but the "success control" decrement trigger runs and moves onto the next part of the program. Everything is symmetrical between success and failure, so if the decrement had failed instead, the example would be the same but with success and failure state swapped. -</p> -<h2><span class="mw-headline" id="The_Amnesiac_From_Minsk.2C_level_2">The Amnesiac From Minsk, level 2</span></h2> -<h3><span class="mw-headline" id="Semantics_2">Semantics</span></h3> -<p>Level 2 works pretty similarly to level 1, with one big difference: instead of a decrement from 1 failing, it succeeds, decrementing the counter to 0. This is known as a "critical state" for the counter (in the sense that bad things can potentially happen very soon); if a counter that's currently at 0 is decremented again, you get <a href="/wiki/Undefined_behaviour" title="Undefined behaviour" class="mw-redirect">undefined behaviour</a>, a state which must be avoided in any valid program. The trigger in the <code>=</code> column has similar semantics as in level 1 – it runs on an attempt to decrement a counter at 1 – but is now called the "critical decrement" rather than "failed decrement" trigger (as the decrement didn't actually fail). (Fans of :≠ will be reminded of the way that that language works, in which you mustn't, say, attempt to disable a function that's already disabled. This language has quite a similar style.) -</p> -<h3><span class="mw-headline" id="Syntax_2">Syntax</span></h3> -<p>The syntax for level 2 is entirely analogous for that at level 1; the semantic changes do not require any syntactic changes. The only difference is that the first line is -<code>L2+=-</code> rather than <code>L1+=-</code>. -</p> -<h3><span class="mw-headline" id="Implementing_level_1_in_level_2">Implementing level 1 in level 2</span></h3> -<p>Making a similar change to a Minsky machine would be trivial; after a critical decrement, you could just increment the counter again then continue what you were doing. It turns out that it's possible to do something similar in The Amnesiac From Minsk (although the construction is a bit more complex due to the absence of an instruction pointer). -</p><p>The idea is to emulate each level 1 counter with a triple of level 2 counters, called "value", "restore", and "increment". While the counter is not being accessed, "value" holds the same value as the level 1 counter being emulated would, and the other two hold 1. The triggers are connected as follows: -</p> -<ul><li> "value" successful-decrement is the same as the emulated counter's successful-decrement trigger</li> -<li> "value" critical-decrement increments "restore"</li> -<li> "value" increment decrements "restore"</li> -<li> "restore" successful-decrement is the same as the emulated counter's failed-decrement trigger</li> -<li> "restore" critical-decrement increments "restore"</li> -<li> "restore" increment decrements "increment"</li> -<li> "increment" successful-decrement is the same as the emulated counter's increment trigger</li> -<li> "increment" critical-decrement increments "increment"</li> -<li> "increment" increment increments "value"</li></ul> -<p>In order to emulate incrementing the counter, we increment "increment": -</p> -<pre>value restore increment - x 1 1 Before starting the increment - x 1 2 Increment starts from outside - x+1 1 2 "value" incremented - x+1 0 2 so it decrements "restore" - x+1 1 2 which increments itself - x+1 1 1 which decrements "increment" -</pre> -<p>and as that was a successful-decrement, we run the increment trigger, as desired. -</p><p>To emulate decrementing the counter, we decrement "value". For a successful-decrement, this is trivial: it decrements successfully and the successful-decrement trigger runs. An emulated failed-decrement is more interesting: -</p> -<pre>value restore increment - 1 1 1 Before starting the decrement - 0 1 1 Decrement starts from outside - 0 2 1 "restore" incremented - 0 2 0 so it decrements "increment" - 0 2 1 which increments itself - 1 2 1 which increments "value" - 1 1 1 which decrements "restore" -</pre> -<p>and now we're back where we started, continuing with the emulated failed-decrement trigger. Which is as we wanted. -</p><p>Because The Amnesiac From Minsk is Turing complete at level 1, and we can compile level 1 into level 2, it's Turing complete at level 2 too. -</p> -<h3><span class="mw-headline" id="Implementing_level_2_in_level_1">Implementing level 2 in level 1</span></h3> -<p>Going the other way is simpler, but not entirely trivial; incrementing a counter after a failed decrement leaves it in a different state from incrementing a counter after a critical decrement. The method we use is to construct signed counters out of pairs of unsigned counters; we have a "positive" and a "negative" counter, with triggers as follows: -</p> -<ul><li> "positive" failed-decrement increments "negative"</li> -<li> "negative" failed-decrement increments "positive"</li> -<li> "positive" successful-decrement is the same as the emulated counter's successful-decrement trigger (because it runs on decrements from 2 or more to 1 or more)</li> -<li> "negative" increment is the same as the emulated counter's critical-decrement trigger (because it runs on decrements from 1 or less to 0 or less)</li> -<li> "positive" increment is the same as the emulated counter's increment trigger (and runs on increments from 1 or more to 2 or more)</li> -<li> "negative" successful-decrement is the same as the emulated counter's increment trigger (and runs on increments from 0 or less to 1 or less)</li></ul> -<p>The two counters effectively encode a single integer, whose value is (positive - negative) + 1, which gives all the behaviour that level 2 needs (while potentially useful for other purposes, too, as the "undefined" behaviour of decrementing a critical trigger is both well-defined and useful in this construction). -</p> -<h2><span class="mw-headline" id="The_Amnesiac_From_Minsk.2C_level_3">The Amnesiac From Minsk, level 3</span></h2> -<h3><span class="mw-headline" id="Semantics_3">Semantics</span></h3> -<p>Unlike levels 1 and 2, in which only one counter is incremented or decremented at a time, a counter adjustment in the level 3 language affects two counters at once. Specifically, incrementing counter <i>x</i> decrements counter <i>x</i>+1, and a decrement cannot be made except via incrementing the previous counter. (The exception is incrementing the last counter; this doesn't cause a counter to be decremented.) The implementation starts running the program via incrementing the first counter, as before, but it now also has the side effect of decrementing the second counter. The first counter starts at 1, and can only go up from there (because there is no way to decrement it). -</p><p>The language otherwise works like the level 2 language; decrementing a counter at 1 is a critical decrement, and that counter thus must not be decremented (and thus the previous counter must not be incremented) until the counter has been restored to a positive value. With the previous-level languages, this would cause problems, as two triggers would run as a result of the two changes. Level 3 does not use increment triggers, just decrement triggers; as a result, you get a successful-decrement or critical-decrement trigger running for the counter that was decremented. Again, the last counter is an exception, and does have an increment trigger, which runs when the last counter is incremented (as no counter is decremented in this case). -</p><p>The I/O (well, output) extension explained above doesn't really work at this level. At present, there's no defined replacement for it, although perhaps one will be added at some point. -</p> -<h3><span class="mw-headline" id="Syntax_3">Syntax</span></h3> -<p>Syntax is basically the same as with levels 1 and 2, but with the increment triggers removed, and with only the increment half of an adjustment shown (and the first line changed to <code>L3=-</code>): -</p> -<pre>L3 = - -1: +2; +1; @5 -2: +0; +3; @9 This is a comment. -3: +1; +0; @12 -+: +1 -</pre> -<p>As can be seen, the last line starts with <code>+:</code> and has a single trigger specified, which is the increment trigger for the last counter. Note also that the first row is labeled <code>1:</code>; the counter numbers still start at 0, but as counter 0 cannot be decremented, there's correspondingly no point in specifying decrement triggers for it. -</p> -<h3><span class="mw-headline" id="Implementing_level_3_in_level_2">Implementing level 3 in level 2</span></h3> -<p>This is pretty trivial; you can use the same counters in level 2 as in level 3, and just have the increment trigger of each counter (but the last) decrement the following counter. As such, level 3 can be seen as a strict subset of level 2; it's level 2 with the additional constraint that all but the last increment trigger has to have a specified value. -</p><p>It's currently not known whether going the other way round (implementing level 2 in level 3) is possible. It seems likely, though; the most promising approach is to place padding counters (that are never allowed to get near 1) between meaningful counters, and to increment and re-decrement counters in order to prevent the padding getting too small. (The main problem is to handle the re-decrement of the "value" counters; the problem is that if you set a counter to remember you're doing a re-decrement, it's hard to treat that counter consistently between an emulated successful decrement and an emulated failed decrement.) -</p> -<h2><span class="mw-headline" id="The_Amnesiac_From_Minsk.2C_level_4">The Amnesiac From Minsk, level 4</span></h2> -<h3><span class="mw-headline" id="Semantics_4">Semantics</span></h3> -<p>Level 4 of The Amnesiac From Minsk is similar to level 3, but with different behaviour for the triggers, and a restriction on the counters as well. The restriction on the counters is that you may never have two critical counters in a row (attempting to create such a situation is undefined behaviour); as with level 3, the first counter always starts at 1 and can only go up from there (although the last counter can go down to 0). As for the triggers, each counter has but a single trigger; the result of the decrement determines which counter's trigger runs: -</p> -<ul><li> If, in an increment/decrement pair, the decrement is critical, then the trigger for the decremented counter runs.</li> -<li> Otherwise, the trigger for the incremented counter runs.</li></ul> -<p>As an extra rule (that's part of the language definition, in order to make the language easier to implement, but which would nonetheless be obeyed by any useful program even if it didn't exist because otherwise some counters couldn't change both up and down), all the triggers that exist must be distinct (i.e. increment different counters). -</p> -<h3><span class="mw-headline" id="Syntax_4">Syntax</span></h3> -<p>Syntax works as in previous levels, with the same sorts of changes; the first line is now <code>L4?</code>, and each line only lists one trigger. There are no longer special cases for the first and last lines. Thus, the language looks like this: -</p> -<pre>L4  ? -0: +2; @1 -1: +0; @9 This is a comment. -2: +1; @12 -3: +3; @5 -</pre> -<h3><span class="mw-headline" id="Implementing_level_4_in_level_3">Implementing level 4 in level 3</span></h3> -<p>Just like implementing level 3 in level 2, this is trivial; you simply copy each of the triggers from the level 4 program into the two corresponding triggers in the level 3 program (apart from the first trigger, which has only one corresponding trigger (the successful-decrement trigger for the second counter) and thus only gets copied to one place). -</p><p>It's currently unknown whether it's possible to go the other way, and implement level 3 in level 4. -</p> -<h3><span class="mw-headline" id="Implementation_in_Last_ReSort">Implementation in Last ReSort</span></h3> -<p>To implement The Amnesiac From Minsk level 4 in <a href="/wiki/Last_ReSort" title="Last ReSort">Last ReSort</a>, we first construct a list of integers from the list of counters by taking a cumulative sum of the initial values of the counters. So for example, if the initial values were (in order) 1, 7, 0, 4, 2, our cumulative sum would be 1, 8, 8, 12, 14. Then we permute the list according to the list of triggers; the element corresponding to the target of the trigger of the last counter comes first, the element corresponding to the target of the trigger of the penultimate counter counter comes second, and so on. The initial pointer points to the element that was permuted from the element corresponding to the first counter (which will always have the value 1). -</p><p>Taking our example from above: -</p> -<pre>L4  ? -0: +2; @1 -1: +0; @9 This is a comment. -2: +1; @12 -3: +3; @5 -</pre> -<p>we get a list [1, 10, 22, 27], which would then be reordered as [27, 10, 1, 22] to provide the Last ReSort program, with the initial pointer pointing to the third element. -</p><p>In order to see how this construction works, consider what one Last ReSort step is doing, when interpreted through the lens of this construction: -</p> -<ul><li> The increment is adding 1 to a single cumulative sum element. This corresponds to incrementing the accumulated element that was added at that point and decrementing the next element (which is exactly how memory changes in The Amnesiac From Minsk level 4).</li> -<li> The retargeting is selecting an element. If the list of cumulative sums were strictly in order (i.e. we accumulated only positive values), then the element that would be selected is the nth from the end, if we incremented counter n (which is exactly the element that's the target of the decremented counter). The only way in which it can fail to be in strict order is if we decremented a counter down to 0, causing its cumulative sum to equal that of the counter afterwards and thus cause the pointer to point at the element before as a consequence of Last Resort's tiebreak rules (corresponding to using the target from the counter afterwards). Note that a three-way tie, which would cause problems, cannot happen because we disallow having two critical counters in a row.</li></ul> -<p>In other words, the two languages are doing the same thing. -</p> -<h2><span class="mw-headline" id="See_also">See also</span></h2> -<ul><li> <a href="/wiki/Minsky_machine" title="Minsky machine">Minsky machine</a></li> -<li> <a href="/wiki/StackFlow" title="StackFlow">StackFlow</a></li> -<li> <a href="/wiki/Unassignable" title="Unassignable">:≠</a></li> -<li> <a href="/wiki/Last_ReSort" title="Last ReSort">Last ReSort</a></li></ul> - -<!-- -NewPP limit report -Cached time: 20170129113539 -Cache expiry: 86400 -Dynamic content: false -CPU time usage: 0.052 seconds -Real time usage: 0.054 seconds -Preprocessor visited node count: 75/1000000 -Preprocessor generated node count: 80/1000000 -Post‐expand include size: 0/2097152 bytes -Template argument size: 0/2097152 bytes -Highest expansion depth: 2/40 -Expensive parser function count: 0/100 ---> - -<!-- -Transclusion expansion time report (%,ms,calls,template) -100.00% 0.000 1 - -total ---> - -<!-- Saved in parser cache with key esolang_wiki:pcache:idhash:10083-0!*!0!!en!*!* and timestamp 20170129113539 and revision id 45748 - --> -</div> <div class="printfooter"> - Retrieved from "<a dir="ltr" href="https://esolangs.org/w/index.php?title=The_Amnesiac_From_Minsk&oldid=45748">https://esolangs.org/w/index.php?title=The_Amnesiac_From_Minsk&oldid=45748</a>" </div> - <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Special:Categories" title="Special:Categories">Categories</a>: <ul><li><a href="/wiki/Category:Languages" title="Category:Languages">Languages</a></li><li><a href="/wiki/Category:Turing_complete" title="Category:Turing complete">Turing complete</a></li><li><a href="/wiki/Category:Output_only" title="Category:Output only">Output only</a></li><li><a href="/wiki/Category:Unimplemented" title="Category:Unimplemented">Unimplemented</a></li><li><a href="/wiki/Category:Cell-based" title="Category:Cell-based">Cell-based</a></li><li><a href="/wiki/Category:Low-level" title="Category:Low-level">Low-level</a></li><li><a href="/wiki/Category:2015" title="Category:2015">2015</a></li></ul></div></div> <div class="visualClear"></div> - </div> - </div> - <div id="mw-navigation"> - <h2>Navigation menu</h2> - - <div id="mw-head"> - <div id="p-personal" role="navigation" class="" aria-labelledby="p-personal-label"> - <h3 id="p-personal-label">Personal tools</h3> - <ul> - <li id="pt-createaccount"><a href="/w/index.php?title=Special:CreateAccount&returnto=The+Amnesiac+From+Minsk" title="You are encouraged to create an account and log in; however, it is not mandatory">Create account</a></li><li id="pt-login"><a href="/w/index.php?title=Special:UserLogin&returnto=The+Amnesiac+From+Minsk" title="You are encouraged to log in; however, it is not mandatory [o]" accesskey="o">Log in</a></li> </ul> - </div> - <div id="left-navigation"> - <div id="p-namespaces" role="navigation" class="vectorTabs" aria-labelledby="p-namespaces-label"> - <h3 id="p-namespaces-label">Namespaces</h3> - <ul> - <li id="ca-nstab-main" class="selected"><span><a href="/wiki/The_Amnesiac_From_Minsk" title="View the content page [c]" accesskey="c">Page</a></span></li> - <li id="ca-talk" class="new"><span><a href="/w/index.php?title=Talk:The_Amnesiac_From_Minsk&action=edit&redlink=1" title="Discussion about the content page [t]" accesskey="t" rel="discussion">Discussion</a></span></li> - </ul> - </div> - <div id="p-variants" role="navigation" class="vectorMenu emptyPortlet" aria-labelledby="p-variants-label"> - <h3 id="p-variants-label"> - <span>Variants</span><a href="#"></a> - </h3> - - <div class="menu"> - <ul> - </ul> - </div> - </div> - </div> - <div id="right-navigation"> - <div id="p-views" role="navigation" class="vectorTabs" aria-labelledby="p-views-label"> - <h3 id="p-views-label">Views</h3> - <ul> - <li id="ca-view" class="selected"><span><a href="/wiki/The_Amnesiac_From_Minsk" >Read</a></span></li> - <li id="ca-viewsource"><span><a href="/w/index.php?title=The_Amnesiac_From_Minsk&action=edit" title="This page is protected. You can view its source [e]" accesskey="e">View source</a></span></li> - <li id="ca-history" class="collapsible"><span><a href="/w/index.php?title=The_Amnesiac_From_Minsk&action=history" title="Past revisions of this page [h]" accesskey="h">View history</a></span></li> - </ul> - </div> - <div id="p-cactions" role="navigation" class="vectorMenu emptyPortlet" aria-labelledby="p-cactions-label"> - <h3 id="p-cactions-label"><span>More</span><a href="#"></a></h3> - - <div class="menu"> - <ul> - </ul> - </div> - </div> - <div id="p-search" role="search"> - <h3> - <label for="searchInput">Search</label> - </h3> - - <form action="/w/index.php" id="searchform"> - <div id="simpleSearch"> - <input type="search" name="search" placeholder="Search" title="Search Esolang [f]" accesskey="f" id="searchInput"/><input type="hidden" value="Special:Search" name="title"/><input type="submit" name="fulltext" value="Search" title="Search the pages for this text" id="mw-searchButton" class="searchButton mw-fallbackSearchButton"/><input type="submit" name="go" value="Go" title="Go to a page with this exact name if it exists" id="searchButton" class="searchButton"/> </div> - </form> - </div> - </div> - </div> - <div id="mw-panel"> - <div id="p-logo" role="banner"><a class="mw-wiki-logo" href="/wiki/Main_Page" title="Visit the main page"></a></div> - <div class="portal" role="navigation" id='p-navigation' aria-labelledby='p-navigation-label'> - <h3 id='p-navigation-label'>Navigation</h3> - - <div class="body"> - <ul> - <li id="n-mainpage-description"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z">Main page</a></li><li id="n-portal"><a href="/wiki/Esolang:Community_portal" title="About the project, what you can do, where to find things">Community portal</a></li><li id="n-Language-list"><a href="/wiki/Language_list">Language list</a></li><li id="n-recentchanges"><a href="/wiki/Special:RecentChanges" title="A list of recent changes in the wiki [r]" accesskey="r">Recent changes</a></li><li id="n-randompage"><a href="/wiki/Special:Random" title="Load a random page [x]" accesskey="x">Random page</a></li><li id="n-help"><a href="/wiki/Esolang:Help" title="The place to find out">Help</a></li> </ul> - </div> - </div> - <div class="portal" role="navigation" id='p-tb' aria-labelledby='p-tb-label'> - <h3 id='p-tb-label'>Tools</h3> - - <div class="body"> - <ul> - <li id="t-whatlinkshere"><a href="/wiki/Special:WhatLinksHere/The_Amnesiac_From_Minsk" title="A list of all wiki pages that link here [j]" accesskey="j">What links here</a></li><li id="t-recentchangeslinked"><a href="/wiki/Special:RecentChangesLinked/The_Amnesiac_From_Minsk" title="Recent changes in pages linked from this page [k]" accesskey="k">Related changes</a></li><li id="t-specialpages"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q">Special pages</a></li><li id="t-print"><a href="/w/index.php?title=The_Amnesiac_From_Minsk&printable=yes" rel="alternate" title="Printable version of this page [p]" accesskey="p">Printable version</a></li><li id="t-permalink"><a href="/w/index.php?title=The_Amnesiac_From_Minsk&oldid=45748" title="Permanent link to this revision of the page">Permanent link</a></li><li id="t-info"><a href="/w/index.php?title=The_Amnesiac_From_Minsk&action=info" title="More information about this page">Page information</a></li> </ul> - </div> - </div> - </div> - </div> - <div id="footer" role="contentinfo"> - <ul id="footer-info"> - <li id="footer-info-lastmod"> This page was last modified on 3 December 2015, at 08:42.</li> - <li id="footer-info-copyright">Content is available under <a href="/wiki/Esolang:Copyrights" title="Esolang:Copyrights">CC0 public domain dedication</a>.</li> - </ul> - <ul id="footer-places"> - <li id="footer-places-about"><a href="/wiki/Esolang:About" title="Esolang:About">About Esolang</a></li> - <li id="footer-places-disclaimer"><a href="/wiki/Esolang:General_disclaimer" title="Esolang:General disclaimer">Disclaimers</a></li> - </ul> - <ul id="footer-icons" class="noprint"> - <li id="footer-copyrightico"> - <a href="http://creativecommons.org/publicdomain/zero/1.0/"><img src="/w/resources/assets/licenses/cc-0.png" alt="CC0 public domain dedication" width="88" height="31"/></a> </li> - <li id="footer-poweredbyico"> - <a href="//www.mediawiki.org/"><img src="/w/resources/assets/poweredby_mediawiki_88x31.png" alt="Powered by MediaWiki" srcset="/w/resources/assets/poweredby_mediawiki_132x47.png 1.5x, /w/resources/assets/poweredby_mediawiki_176x62.png 2x" width="88" height="31"/></a> </li> - </ul> - <div style="clear:both"></div> - </div> - <script>(window.RLQ=window.RLQ||[]).push(function(){mw.loader.state({"user":"ready","user.groups":"ready"});mw.loader.load(["mediawiki.toc","mediawiki.action.view.postEdit","site","mediawiki.user","mediawiki.hidpi","mediawiki.page.ready","mediawiki.searchSuggest"]);});</script><script>(window.RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgBackendResponseTime":181});});</script> - </body> -<!-- Cached 20170129113539 --> -</html>