103 def run(tp: Tape) : Tape = run(Config(1, tp)).tp |
103 def run(tp: Tape) : Tape = run(Config(1, tp)).tp |
104 } |
104 } |
105 |
105 |
106 |
106 |
107 |
107 |
108 // examples |
108 // Turing machine examples |
109 val TMCopy = TM(List((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3), |
109 val TMCopy = TM(List((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3), |
110 (L, 4), (L, 4), (L, 5), (R, 11), (R, 6), |
110 (L, 4), (L, 4), (L, 5), (R, 11), (R, 6), |
111 (R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9), |
111 (R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9), |
112 (R, 8), (L, 10), (L, 9), (L, 10), (L, 5), |
112 (R, 8), (L, 10), (L, 9), (L, 10), (L, 5), |
113 (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12), |
113 (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12), |
141 println("TMCopy: " + (TMCopy.run(new STape(3)))) |
141 println("TMCopy: " + (TMCopy.run(new STape(3)))) |
142 println("TMfindnth: " + (TMFindnth(3).run(new STape(1,2,3,4,5)))) |
142 println("TMfindnth: " + (TMFindnth(3).run(new STape(1,2,3,4,5)))) |
143 println("TMMopup: " + (TMMopup(3).run(new STape(1,2,3,4,5)))) |
143 println("TMMopup: " + (TMMopup(3).run(new STape(1,2,3,4,5)))) |
144 |
144 |
145 |
145 |
146 // Abacus |
146 // Abacus machines |
147 abstract class AInst |
147 abstract class AInst |
148 case class Inc(n: Int) extends AInst |
148 case class Inc(n: Int) extends AInst |
149 case class Dec(n: Int, l: Int) extends AInst |
149 case class Dec(n: Int, l: Int) extends AInst |
150 case class Goto(l: Int) extends AInst |
150 case class Goto(l: Int) extends AInst |
151 |
151 |
|
152 // shifting and adjusting labels |
152 def ashift(ai: AInst, offset: Int, jump: Int) = ai match { |
153 def ashift(ai: AInst, offset: Int, jump: Int) = ai match { |
153 case Inc(n) => Inc(n) |
154 case Inc(n) => Inc(n) |
154 case Dec(n, l) => if (l == jump) Dec(n, l) else Dec(n, l + offset) |
155 case Dec(n, l) => if (l == jump) Dec(n, l) else Dec(n, l + offset) |
155 case Goto(l) => if (l == jump) Goto(l) else Goto(l + offset) |
156 case Goto(l) => if (l == jump) Goto(l) else Goto(l + offset) |
156 } |
157 } |
195 } |
196 } |
196 |
197 |
197 def run(regs: Regs): Regs = run(AConfig(0, regs)).regs |
198 def run(regs: Regs): Regs = run(AConfig(0, regs)).regs |
198 } |
199 } |
199 |
200 |
200 // examples |
201 // Abacus examples |
201 def Copy(in: Int, out: Int) = |
202 def Copy(in: Int, out: Int, jump: Int) = |
202 Abacus(List(Dec(in, -1), Inc(out), Goto(0))) |
203 Abacus(List(Dec(in, jump), Inc(out), Goto(0))) |
203 |
204 |
204 def Plus(m: Int, n: Int, tmp: Int, jump: Int) = |
205 def Plus(m: Int, n: Int, tmp: Int, jump: Int) = |
205 Abacus(List(Dec(m, 4), Inc(n), Inc(tmp), |
206 Abacus(List(Dec(m, 4), Inc(n), Inc(tmp), |
206 Goto(0), Dec(tmp, jump), Inc(m), Goto(4))) |
207 Goto(0), Dec(tmp, jump), Inc(m), Goto(4))) |
207 |
208 |
208 def Mult(in1: Int, in2: Int, out: Int, tmp: Int, jump: Int) = { |
209 def Mult(in1: Int, in2: Int, out: Int, tmp: Int, jump: Int) = { |
209 val tm = Plus(in2, out, tmp, -1).shift(1, -1).adjust(-1, 0) |
210 val tm = Plus(in2, out, tmp, -1).shift(1, -1).adjust(-1, 0) |
210 Abacus(Dec(in1, jump) :: tm.p) |
211 Abacus(Dec(in1, jump) :: tm.p) |
211 } |
212 } |
212 |
213 |
213 def Expo(in1: Int, in2: Int, out: Int, tmp: Int, jump: Int) = { |
214 def Expo(in1: Int, in2: Int, out: Int, tmp1: Int, tmp2: Int, jump: Int) = { |
214 val tm = Plus(in2, out, tmp, -1).shift(1, -1).adjust(-1, 0) |
215 val tm1 = Mult(out, in2, tmp2, tmp1, -1).shift(2, -1).adjust(-1, 10) |
215 Abacus(Dec(in1, jump) :: tm.p) |
216 val tm2 = Copy(tmp2, out, -1).shift(10, -1). adjust(-1, 1) |
216 } |
217 Abacus(Inc(out) :: Dec(in1, jump) :: tm1.p ::: tm2.p) |
217 |
218 } |
218 |
219 |
219 println("Copy: " + (Copy(0, 1).run(Map(0 -> 3, 1 -> 0)))) |
220 |
220 println("Plus: " + (Plus(0, 1, 2, -1).run(Map(0 -> 3, 1 -> 4, 2 -> 0)))) |
221 println("Copy: " + (Copy(0, 1, -1).run(Map(0 -> 3, 1 -> 0)))) |
221 println("Mult: " + (Mult(0, 1, 2, 3, -1).run(Map(0 -> 3, 1 -> 5, 2 -> 0, 3 -> 0)))) |
222 println("Plus: 3 + 4 " + (Plus(0, 1, 2, -1).run(Map(0 -> 3, 1 -> 4, 2 -> 0)))) |
222 |
223 println("Mult: 3 * 5 " + (Mult(0, 1, 2, 3, -1).run(Map(0 -> 3, 1 -> 5, 2 -> 0, 3 -> 0)))) |
223 |
224 println("Expo: 3 ^ 4 " + (Expo(0, 1, 2, 3, 4, -1).run(Map(0 -> 4, 1 -> 3, 2 -> 0, 3 -> 0, 4 -> 0)))) |
224 |
225 |
225 //Recursive Functions |
226 //Recursive Functions |
226 abstract class Rec { |
227 abstract class Rec { |
227 def eval(ns: List[Int]) : Int |
228 def eval(ns: List[Int]) : Int |
228 } |
229 } |