Code.LJ

: codedot; May 16th, 1:05

https://twitter.com/codedot/status/334919626125357056
https://www.facebook.com/codedot/posts/578694112152413

Task statement

Implements cache for Schönhage's RAM0 to execute any sequence of n instructions from {Z, A, L, N, S} without memory access.

RFC.

This entry was originally posted at http://codedot.dreamwidth.org/160650.html

Tags: computers, elementary mathematics, ideas, lambda calculus

Компиляция из MLC в RAM0

: codedot; May 15th, 15:23

Программы на языке MLC (Macro Lambda Calculus) - пример доступен на GitHub - имеют следующий вид:

N1 = M1;
...
Nm = Mm;

M0.

Выражение M0 может содержать произвольное число вхождений имен макросов N1, ... , Nm, а также свободных переменных - обозначим их x1, ... , xn. Комбинатор M, нормальную форму которого мы фактически ищем, получается из программы следующим образом:

M = x1, ... , xn: (N1, ... , Nm: M0) M1 ... Mm.

Комбинатор M, в свою очередь, представим в исчислении взаимодействия, воспользовавшись направленной версией компактной кодировки λ-выражений. Заметим, что конфигурация <x | Γ(M, x)>, как можно видеть из определения, содержит только редексы по левому разыменованию. Следовательно, чтобы инициализировать нашу систему слепой перезаписи графов, достаточно все уравнения конфигурации положить в стек, соответствующий левому разыменованию.

Полученную в результате структуру памяти можно восстановить некоторой последовательностью I инструкций Z, A, L, N и S машины RAM0. Основной цикл работы нашей системы слепой перезаписи графов, реализующей редукцию сетей взаимодействия, также может быть представлен некоторой последовательностью R инструкций Z, A, L, N и S, которая не зависит от вычисляемого выражения. Таким образом, исходный код на языке MLC может быть скомпилирован в следующую программу RAM0:

I;
loop: R;
goto loop;

Данная программа не содержит инструкцию C для условного перехода. Такие детали, как стратегия вычисления, остановка машины, обработка дна стеков и механизм "read-back" во время стягивания конфигурации, были здесь намеренно опущены, чтобы не нагромождать и без того уже объемное изложение.

This entry was originally posted at http://codedot.dreamwidth.org/160328.html

Tags: elementary mathematics, ideas, lambda calculus, programming

RAM0

: codedot; May 14th, 13:11

Модель RAM0 (Schönhage's zero-parameter successor RAM model) - это компьютер с двумя регистрами (z и n) и шестью командами (Z, A, L, N, S и C), который эквивалентен SMM (Schönhage's storage modification machine model).

Как следует из названия, команды RAM0, за исключением, пожалуй, условного перехода, не имеют параметров. Одна из ее особенностей - алгоритм умножения n-битных чисел за линейное время O(n). Этот, на первый взгляд, парадоксальный результат говорит о том, что механизм RAM сам по себе обладает определенной вычислительной мощностью.

На языке Си команды RAM0 выглядят следующим образом:

#ifndef _RAM0_H
#define _RAM0_H

#include <stdlib.h>

extern void **n, **z;

#define Z	z = NULL
#define A	++z
#define L	z = *z
#define N	n = z
#define S	*n = z

#define C(label) \
	do { \
		if (z) \
			goto label; \
	} while (0)

#endif

Ниже пример программы:

#include "ram0.h"

void **n, **z;

main()
{
	loop: Z; A; L; N; S; C(loop);

	return !z;
}

Интересно, что система сохраняет Тьюринг-полноту, даже если заменить условный переход безусловным. Эта задача рассматривается в статьях "Blind graph rewriting systems" и "A compact encoding for λ-terms in interaction calculus".

This entry was originally posted at http://codedot.dreamwidth.org/160095.html

Tags: elementary mathematics, lambda calculus

Primer vs. Premonition

: codedot; May 12th, 12:58

This entry was originally posted at http://codedot.dreamwidth.org/159822.html

Tags: entertainment, favorites

Schönhage’s SMM with only one instruction

: codedot; May 7th, 6:32

http://mathoverflow.net/questions/129923

It is possible to implement λ-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions set w to v (with different w and v) using a compact directed encoding for λ-terms closely related to directed interaction combinators by Lafont, and four infinite spaghetti stacks based on linked nodes to perform interaction and indirection rules on configurations.

Is it possible to preserve Turing-completeness of the SMM model while restricting its instruction set to only a single instruction set w to v (with constant w and v) during the whole computation process?

I would be very grateful for any references regarding this question.

This entry was originally posted at http://codedot.dreamwidth.org/159655.html

Tags: elementary mathematics, lambda calculus, talks

Schönhage's Storage Modification Machine

: codedot; May 6th, 18:24

In theoretical computer science a pointer machine is an "atomistic" abstract computational machine model akin to the Random access machine.

Depending on the type, a pointer machine may be called a linking automaton, a KU-machine, an SMM, an atomistic LISP machine, a tree-pointer machine, etc. (cf Ben-Amram 1995). At least three major varieties exist in the literature—the Kolmogorov-Uspenskii model (KUM, KU-machine), the Knuth linking automaton, and the Schönhage Storage Modification Machine model (SMM). The SMM seems to be the most common.

This should definitely help to answer two questions on MathOverflow, regarding Turing-complete primitive blind automata and Universality of blind graph rewriting.

This entry was originally posted at http://codedot.dreamwidth.org/159338.html

Tags: elementary mathematics, lambda calculus, talks

Hidden SSH

: codedot; May 3rd, 20:36

root@debian:~# apt-get install tor
Reading package lists... Done
Building dependency tree       
Reading state information... Done
[...]
root@debian:~# grep '^Hidden' /etc/tor/torrc
HiddenServiceDir /var/lib/tor/honey/
HiddenServicePort 22 127.0.0.1:22
root@debian:~# /etc/init.d/tor restart
Stopping tor daemon: tor.
Raising maximum number of filedescriptors (ulimit -n) to 8192.
Starting tor daemon: tor...
[...]
May 03 20:08:30.201 [notice] Opening Socks listener on 127.0.0.1:9050
done.
root@debian:~# torsocks ssh `cat /var/lib/tor/honey/hostname`
root@ohdzjoric6qwtr2c.onion's password: 
Linux debian 2.6.32-5-amd64 #1 SMP Mon Feb 25 00:26:11 UTC 2013 x86_64

The programs included with the Debian GNU/Linux system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.

Debian GNU/Linux comes with ABSOLUTELY NO WARRANTY, to the extent
permitted by applicable law.
Last login: Fri May  3 20:10:22 2013 from localhost
root@debian:~# dd if=/dev/urandom of=data count=1k
1024+0 records in
1024+0 records out
524288 bytes (524 kB) copied, 0.081219 s, 6.5 MB/s
root@debian:~# md5sum data
81d52fca4cfe42dca24659850139672a  data
root@debian:~# logout # latency about 1-2 sec.
Connection to ohdzjoric6qwtr2c.onion closed.
root@debian:~# torsocks scp `cat /var/lib/tor/honey/hostname`:data copy
root@ohdzjoric6qwtr2c.onion's password: 
data                                          100%  512KB  28.4KB/s   00:18    
root@debian:~# md5sum copy
81d52fca4cfe42dca24659850139672a  copy
root@debian:~#

This entry was originally posted at http://codedot.dreamwidth.org/159011.html

Tags: computers, howtos

Bitcoin Proof of Work in Command Line

: codedot; April 25th, 13:45

$ cat hex 
02000000
f40457b1
d005aeec
6e4fe577
f2a76dc3
73ef8901
220376b7
2b6de55a
00000000
bdcb52b0
9c48d2ee
26a513cb
cead7fb7
7daf4cef
9e2ab83b
bb9eb6b0
a7f5f990
fd270c51
378a0e1c
381353fa
$ xxd -r -p hex data
$ shasum -a 256 data >hash1
$ xxd -r -p hash1 bin
$ shasum -a 256 bin
e340423dffb20d7d21f17dfa272c527d84c20662061ce635627d0f0200000000  bin
$

This entry was originally posted at http://codedot.dreamwidth.org/158739.html

Tags: howtos, ideas, programming

Time Travel in Primer

: codedot; April 24th, 8:44

This entry was originally posted at http://codedot.dreamwidth.org/158660.html

Tags: entertainment, favorites

Поведение операции на функциях, меняющей одну точку

: codedot; April 22nd, 15:09

http://mathoverflow.net/questions/128354/

Пусть n ∈ N, и s: N → N, p: (N → N) → N определены следующим образом:

s(x) = x + 1;
p(f) = c(1),

где c - композиция функций s и f.

Теперь рассмотрим операцию φ: (N → N) → (N → N), такую, что если g = φ(f), то

g(x) = f(x), x ≠ fⁿ(1);
g(x) = p(f), x = fⁿ(1).

Что можно сказать о поведении φ^k(f) при k → ∞ в зависимости от выбора n и p?

This entry was originally posted at http://codedot.dreamwidth.org/158233.html

Tags: elementary mathematics, talks

Previous 10

codedot

Code.LJ

README