{"id":289,"date":"2007-01-26T10:20:29","date_gmt":"2007-01-26T10:20:29","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/01\/26\/a-pathological-challenge-prime-programming-in-null\/"},"modified":"2007-01-26T10:20:29","modified_gmt":"2007-01-26T10:20:29","slug":"a-pathological-challenge-prime-programming-in-null","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/01\/26\/a-pathological-challenge-prime-programming-in-null\/","title":{"rendered":"A Pathological Challenge: Prime Programming in NULL"},"content":{"rendered":"

Todays pathological language is actually in the form of a challenge for you. (Isn’t that
\nexciting?) It’s a very clever numerical programming language in the vein of Conway’s Fractran<\/a>,
\ncalled NULL<\/a>. The author of NULL describes it
\nas a reaction to 2 and 3 dimensional languages in the Befunge tradition; NULL is a 0<\/em>
\ndimensional language – a program is just a single point. It’s quite clever in its way; the only
\nproblem is that is that there’s only one<\/em> example program written in it. So the challenge is
\nto see if you can actually come up with some implementations of interesting programs. <\/p>\n

<\/p>\n

A program in NULL is a single very large number. The way that it executes is dependent
\non its prime factorization, as in Fractran. But NULL is more expressive than Fractran; it’s
\na real programming language with input and output.<\/p>\n

In a NULL program, you actually have 3 queues containing bytes of which one is the
\ncurrent<\/em> queue at any particular time, and two registers that can contain arbitrarily large
\nintegers. The queues are named by number: 0, 1, and 2; and the registers are named X and Y. When the
\nprogram starts, the X register contains the program, and the Y register contains the number 1, all
\nthree queues are empty, and the current queue is 0.<\/p>\n

Program execution in NULL is a simple loop:<\/p>\n

\nwhile (X<\/b> != 0 and X<\/b> != 1) do\nlet op<\/em> be the smallest prime factor of X<\/b>.\nX<\/b> = X<\/b>\/op<\/em>\nY<\/b> = Y<\/b>×op<\/em>\nexecute opcode op<\/em>\nend\n<\/pre>\n
 Every prime number is interpreted as an opcode. Since there are only 14 opcodes, the way that it
\nworks is that the opcodes cycle over the primes – so, for example, both 2 (the first prime) and 47 (the 15th prime) are the same opcode. The opcodes are:<\/p>\n
\n
2: Next<\/dt>\n
 Switch the current queue to the next, wrapping around from 2 to 0.<\/dd>\n
3: Previous<\/dt>\n
 Switch the current queue to the previous, wrapping around from 0 to 2.<\/dd>\n
5: Output<\/dt>\n
 Output the character from the front of the current queue.<\/dd>\n
7: Input<\/dt>\n
Input one character, and replace<\/em> the byte at the front of the current queue with it.<\/dd>\n
11: Subtract<\/dt>\n
Subtract the byte at the front of the current queue from Y. (If the result is less than 0,
\nthen set Y to 0.)<\/dd>\n
13: Add<\/dt>\n
Add the byte at the front of the current queue to Y.<\/dd>\n
17: AddY<\/dt>\n
Add the lowest-order byte of Y to the byte at the front of the current queue.<\/dd>\n
19: RotateRight<\/dt>\n
Remove the byte at the front of the current queue, and append it to the tail of the next queue.<\/dd>\n
23: RotateLeft<\/dt>\n
Remove the byte at the front of the current queue, and append it to the tail of the previous queue.<\/dd>\n
29: Discard<\/dt>\n
Remove the first byte from the current queue and discard.<\/dd>\n
31: Enqueue<\/dt>\n
Enqueue the lower-order byte of Y to the tail of the current queue.<\/dd>\n
37: Drop<\/dt>\n
 If the selected queue is empty, or it first byte is 0, then find the smallest prime factor p of X, set X = X\/p, and set Y = Y×p.<\/dd>\n
41: Swap<\/dt>\n
 Swap X and Y.<\/dd>\n
43: Halt<\/dt>\n
Halt<\/dd>\n<\/dl>\n
 If you look at the instructions, you should be able to see that it’s Turing-equivalent. You can do loops, because each instruction is added to Y as it’s removed from X – so by swapping X and Y using Swap<\/b>, you repeat a loop iteration. You can skip instructions – effectively doing a conditional, using Drop<\/b>. You can modify the program, adding or removing instructions, using Add<\/b> and Subtract<\/b>. And the queues clearly provide unbounded storage. So we’ve got an effective computing system here. Just an incredibly devious one.<\/p>\n
 The one sample program is a hello world. It’s the number:<\/p>\n
\n15360939363786950397128283933599538624\n89217432048303485700335501579138988589\n76126298703504031567456769368158187308\n36908075646108694411913908753341542249\n057283074613678144889367\n<\/pre>\n
 There’s an implementation of NULL in Python available here<\/a>.<\/p>\n
 So – anyone up to implementing something simple like a Fibonacci series generator, or a factorial program?<\/p>\n","protected":false},"excerpt":{"rendered":"
Todays pathological language is actually in the form of a challenge for you. (Isn’t that exciting?) It’s a very clever numerical programming language in the vein of Conway’s Fractran, called NULL. The author of NULL describes it as a reaction to 2 and 3 dimensional languages in the Befunge tradition; NULL is a 0 dimensional […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[92],"tags":[],"class_list":["post-289","post","type-post","status-publish","format-standard","hentry","category-pathological-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-4F","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/289","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=289"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/289\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=289"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=289"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=289"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}