--- a/turing.scala Mon Feb 18 13:33:00 2013 +0000
+++ b/turing.scala Mon Feb 18 14:39:50 2013 +0000
@@ -69,7 +69,7 @@
}
-// Turing Machines
+// Turing machines
case class TM(p: Prog) {
def shift(n: Int) =
@@ -105,7 +105,7 @@
-// examples
+// Turing machine examples
val TMCopy = TM(List((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3),
(L, 4), (L, 4), (L, 5), (R, 11), (R, 6),
(R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9),
@@ -143,12 +143,13 @@
println("TMMopup: " + (TMMopup(3).run(new STape(1,2,3,4,5))))
-// Abacus
+// Abacus machines
abstract class AInst
case class Inc(n: Int) extends AInst
case class Dec(n: Int, l: Int) extends AInst
case class Goto(l: Int) extends AInst
+// shifting and adjusting labels
def ashift(ai: AInst, offset: Int, jump: Int) = ai match {
case Inc(n) => Inc(n)
case Dec(n, l) => if (l == jump) Dec(n, l) else Dec(n, l + offset)
@@ -197,9 +198,9 @@
def run(regs: Regs): Regs = run(AConfig(0, regs)).regs
}
-// examples
-def Copy(in: Int, out: Int) =
- Abacus(List(Dec(in, -1), Inc(out), Goto(0)))
+// Abacus examples
+def Copy(in: Int, out: Int, jump: Int) =
+ Abacus(List(Dec(in, jump), Inc(out), Goto(0)))
def Plus(m: Int, n: Int, tmp: Int, jump: Int) =
Abacus(List(Dec(m, 4), Inc(n), Inc(tmp),
@@ -210,17 +211,17 @@
Abacus(Dec(in1, jump) :: tm.p)
}
-def Expo(in1: Int, in2: Int, out: Int, tmp: Int, jump: Int) = {
- val tm = Plus(in2, out, tmp, -1).shift(1, -1).adjust(-1, 0)
- Abacus(Dec(in1, jump) :: tm.p)
+def Expo(in1: Int, in2: Int, out: Int, tmp1: Int, tmp2: Int, jump: Int) = {
+ val tm1 = Mult(out, in2, tmp2, tmp1, -1).shift(2, -1).adjust(-1, 10)
+ val tm2 = Copy(tmp2, out, -1).shift(10, -1). adjust(-1, 1)
+ Abacus(Inc(out) :: Dec(in1, jump) :: tm1.p ::: tm2.p)
}
-println("Copy: " + (Copy(0, 1).run(Map(0 -> 3, 1 -> 0))))
-println("Plus: " + (Plus(0, 1, 2, -1).run(Map(0 -> 3, 1 -> 4, 2 -> 0))))
-println("Mult: " + (Mult(0, 1, 2, 3, -1).run(Map(0 -> 3, 1 -> 5, 2 -> 0, 3 -> 0))))
-
-
+println("Copy: " + (Copy(0, 1, -1).run(Map(0 -> 3, 1 -> 0))))
+println("Plus: 3 + 4 " + (Plus(0, 1, 2, -1).run(Map(0 -> 3, 1 -> 4, 2 -> 0))))
+println("Mult: 3 * 5 " + (Mult(0, 1, 2, 3, -1).run(Map(0 -> 3, 1 -> 5, 2 -> 0, 3 -> 0))))
+println("Expo: 3 ^ 4 " + (Expo(0, 1, 2, 3, 4, -1).run(Map(0 -> 4, 1 -> 3, 2 -> 0, 3 -> 0, 4 -> 0))))
//Recursive Functions
abstract class Rec {