 Basic ECL is Turing-complete: Here's the proof [message #1705315] |
Thu, 13 August 2015 17:37 |
 Joshua Robbins
Messages: 1
Registered: August 2015 |
Junior Member |
|
|
I was busy one day, writing ECL tests, when I wondered exactly how powerful ECL is. Of course, with the RCPTT extension that allows you to invoke arbitrary Java functions, it can do anything Java can. However, if you remove these Java interface commands, can you still use ECL to compute things?
The answer is yes: Given infinite memory space, ECL is Turing-complete.
I'm not much for formal proofs, so I did the next-best thing; I wrote an interpreter for Brainfuck in ECL. Since Brainfuck is known to be Turing-complete, any language that can implement it without restriction is also Turing-complete.
Below is the code that does the work. All you have to do is take a BF program, turn each symbol into a numerical constant ($PLUS, $LEFT, etc.) , and paste it into the list elements of $input. The code below is pre-loaded with the famous "Hello, World" program.
Cells have values limited to the range of ECL integers (which I presume are 32-bit Java ints, but I have not looked into this). The tape is unbounded to both the left and right. Output is displayed in decimal for each character displayed. Input is a no-op, but that's okay, because it doesn't factor into BF's Turing-completeness.
The code could use a lot of cleaning up. Sorry. Anyways, here's the BF interpreter:
/*
BF interpreter v1.0
author: Joshua Robbins (@iconmaster5326)
*/
proc "find-tape" [val tape] [val key] {
let [val len [$tape | each [val v] {
$v
} | length]] {
loop [val i 0] {
if [$i | lt $len] {
if [$tape | get $i | get 0 | equals $key] {
bool true
} -else {
recur [$i | plus 1]
}
} -else {
bool false
}
}
}
}
proc "set-tape" [val tape] [val key] [val value] {
$tape | each [val v] {
if [$v | get 0 | equals $key] {
list $key $value
} -else {
$v
}
} | to-list
}
proc "add-tape" [val tape] [val key] [val value] {
$tape | each [val v] [val i] {
if [$i | equals 0] {
emit [list $key $value] $v
} -else {
emit $v
}
} | to-list
}
proc "get-tape" [val tape] [val key] {
let [val len [$tape | each [val v] {
$v
} | length]] {
loop [val i 0] {
if [$i | lt $len] {
if [$tape | get $i | get 0 | equals $key] {
emit [$tape | get $i | get 1]
} -else {
recur [$i | plus 1]
}
} -else {
emit 0
}
}
}
}
proc "update-tape" [val tape] [val key] [val val] {
if [find-tape $tape $key] {
set-tape $tape $key $val
} -else {
add-tape $tape $key $val
}
}
global [val PLUS 1] // +
global [val MINUS 2] // -
global [val LEFT 3] // <
global [val RIGHT 4] // >
global [val BEGIN 5] // [
global [val END 6] // ]
global [val DISP 7] // .
global [val INPUT 8] // ,
let [val input [list $PLUS $PLUS $PLUS $PLUS $PLUS $PLUS $PLUS $PLUS $BEGIN $RIGHT $PLUS $PLUS $PLUS $PLUS $BEGIN $RIGHT $PLUS $PLUS $RIGHT $PLUS $PLUS $PLUS $RIGHT $PLUS $PLUS $PLUS $RIGHT $PLUS $LEFT $LEFT $LEFT $LEFT $MINUS $END $RIGHT $PLUS $RIGHT $PLUS $RIGHT $MINUS $RIGHT $RIGHT $PLUS $BEGIN $LEFT $END $LEFT $MINUS $END $RIGHT $RIGHT $DISP $RIGHT $MINUS $MINUS $MINUS $DISP $PLUS $PLUS $PLUS $PLUS $PLUS $PLUS $PLUS $DISP $DISP $PLUS $PLUS $PLUS $DISP $RIGHT $RIGHT $DISP $LEFT $MINUS $DISP $LEFT $DISP $PLUS $PLUS $PLUS $DISP $MINUS $MINUS $MINUS $MINUS $MINUS $MINUS $DISP $MINUS $MINUS $MINUS $MINUS $MINUS $MINUS $MINUS $MINUS $DISP $RIGHT $RIGHT $PLUS $DISP $RIGHT $PLUS $PLUS $DISP]] {
loop [val tape [list [list 0 0]]] [val head 0] [val pc 0] {
try {
$input | get $pc
bool true
} -catch {
bool false
} | let [val more -input] {
if [$more] {
$input | get $pc | switch [case $PLUS {
recur [update-tape $tape $head [get-tape $tape $head | plus 1]] $head [$pc | plus 1]
}] [case $MINUS {
recur [update-tape $tape $head [get-tape $tape $head | minus 1]] $head [$pc | plus 1]
}] [case $LEFT {
recur $tape [$head | minus 1] [$pc | plus 1]
}] [case $RIGHT {
recur $tape [$head | plus 1] [$pc | plus 1]
}] [case $BEGIN {
if [get-tape $tape $head | equals 0] {
//go forward to matching ]
loop [val npc $pc] [val depth 0] {
$input | get $npc | switch [case $BEGIN {
recur [$npc | plus 1] [$depth | plus 1]
}] [case $END {
if [$depth | eq 1] {
$npc
} -else {
recur [$npc | plus 1] [$depth | minus 1]
}
}] -default {
recur [$npc | plus 1] $depth
}
} | let [val npc -input] {
recur $tape $head [$npc | plus 1]
}
} -else {
recur $tape $head [$pc | plus 1]
}
}] [case $END {
if [get-tape $tape $head | equals 0] {
recur $tape $head [$pc | plus 1]
} -else {
//go back to matching [
loop [val npc $pc] [val depth 0] {
$input | get $npc | switch [case $END {
recur [$npc | minus 1] [$depth | plus 1]
}] [case $BEGIN {
if [$depth | eq 1] {
$npc
} -else {
recur [$npc | minus 1] [$depth | minus 1]
}
}] -default {
recur [$npc | minus 1] $depth
}
} | let [val npc -input] {
recur $tape $head [$npc | plus 1]
}
}
}] [case $DISP {
get-tape $tape $head | show-alert
recur $tape $head [$pc | plus 1]
}] [case $INPUT {
//input is not supported, sadly
recur $tape $head [$pc | plus 1]
}] -default {
concat "ERROR: Unknown opcode " [$input | get $pc] "!" | show-alert
recur $tape $head [$pc | plus 1]
}
} -else {
emit "Program finished." | show-alert
}
}
}
}
[Updated on: Thu, 13 August 2015 17:59] Report message to a moderator |
|
|
Powered by
FUDForum. Page generated in 0.02580 seconds
] 
Search
Help
Register
Login
Home
