lambdaway
::
tm
2
|
list
|
login
|
load
|
|
_img https://upload.wikimedia.org/wikipedia/commons/3/3d/Maquina.png _h1 the turing machine {sup {sup (lambdatalk version)}} _ul [[Javascript version|?view=turing_machine]]. _ul Lambda-calculus approach in [[fromroots2canopy]]. _p One of the foundational mathematical constructs behind computer science is the {b Universal Turing Machine}. Indeed one way to definitively prove that a language is turing-complete is to implement a universal Turing machine in it. _p According to [[rosettacode.org|http://rosettacode.org/wiki/Universal_Turing_machine#Lambdatalk]] " {i the task is to simulate such a machine capable of taking the definition of any other Turing machine, some set of rules, and executing it.}" Of course, you will not have an infinite tape, but you should emulate this as much as is possible. The three permissible actions on the tape are "left", "right" and "stay". To test your universal Turing machine (and prove your programming language is Turing complete!), you should execute two or three Turing machines based on the definitions detailed in [[rosettacode.org|http://rosettacode.org/wiki/Universal_Turing_machine#Lambdatalk]]. _img https://upload.wikimedia.org/wikipedia/commons/thumb/4/43/Universal_Turing_machine.svg/2880px-Universal_Turing_machine.svg.png _h2 1) the tm function _p The {b tm} function is a universal Turing machine, a window sliding back and forth on an {b infinite stripe} made of {b blank} cells created on demand, some of them containing an initial set of symbols, {b datas}, rewrites them according to a set of {b rules}, from an initial {b state} to a final one, {b end}, if any, and returns the final state of datas. _p Lambdatalk comes with indexed arrays but has no associative arrays (hashes) in its kernel, [[meta/JS.js]]. We have built a reduced implementation of hashes in the [[lib_hash]] library, which is loaded in the current page via the {code require} command. The {b tm} function does some initializations then calls a recursive function, {b tm.r} scanning the cells and writing, moving and modifying states according to the set of rules. ;; { require lib_hash} {pre '{def tm {def tm.r // loop {lambda {:data :rules :state :end :blank :i :N} {if {or {W.equal? :state :end} {> :N 100}} // stop if N > 100 then :data // return final data else {let { {:data :data} {:rules :rules} // reassign outern {:end :end} {:blank :blank} {:i :i} {:N :N} // variables {:state {H.get :rules :state}} // change state {:cell {if {W.equal? {A.get :i :data} undefined} // get cell then :blank // if defined else {A.get :i :data}}} // else set blank } {tm.r {A.set! :i // set {H.get {H.get :state :cell} write} // new cell :data} // in data :rules {H.get {H.get :state :cell} next} // set next :end :blank {+ :i {H.get {H.get :state :cell} move} } // move {+ :N 1} } // next one }}}} {lambda {:name :data :rules :state :end :blank} :name: {A.duplicate :data} -> // display name and initial data {tm.r :data :rules :state :end :blank 0 0} // init i and N and and loop }} -> {def tm {def tm.r {lambda {:data :rules :state :end :blank :i :N} {if {or {W.equal? :state :end} {> :N 100}} then :data else {let { {:name :name} {:data :data} {:end :end} {:blank :blank} {:rules :rules} {:i :i} {:N :N} {:state {H.get :rules :state}} {:cell {if {W.equal? {A.get :i :data} undefined} then :blank else {A.get :i :data}}} } {tm.r {A.set! :i {H.get {H.get :state :cell} write} :data} :rules {H.get {H.get :state :cell} next} :end :blank {+ :i {H.get {H.get :state :cell} move} } {+ :N 1} } }}}} {lambda {:name :data :rules :state :end :blank} :name: {A.duplicate :data} -> {tm.r :data :rules :state :end :blank 0 0}}} } _h2 2) testing several rules _p The universal machine will be tested for several sets of rules: {pre '{tm name // display the name of the given turing machine data // a given array {A.new ...} containing the initial symbols rules // a given associative array containing the initial rules // for writing in the current cell, // moving along the stripe, +1, 0, -1 // and changing the rule state // the initial state end // the final state (eventually non reached -> infinite loop) blank // the character marking an empty cell } } _h3 2.1) replacing zeros by ones {pre 1) the initial data is an infinite stripe . . . 0 0 0 . . . coded as a finite array [0,0,0] 2) the head starts on the first "0", 3) if the head is on an undefined cell "." a blank symbol "B" is written 4) the initial state is A which says: 5) if the cell contains "0" then write "1", move right and goto A if the cell contains "B" then write ".", don't move and halt 6) the final data is . . . 1 1 1 . . . '{tm zero2one {A.new 0 0 0} {H.new A {H.new 0 {H.new write 1 | move 1 | next A} | B {H.new write . | move 0 | next H} } } A H B} output: {tm zero2one {A.new 0 0 0} {H.new A {H.new 0 {H.new write 1 | move 1 | next A} | B {H.new write . | move 0 | next H} } } A H B} } _h3 2.2) adding one to a set of ones {pre '{tm add_one {A.new 1 1 1} {H.new A {H.new 1 {H.new write 1 | move 1 | next A} | B {H.new write 1 | move 0 | next B} } } A B B} output: {tm add_one {A.new 1 1 1} {H.new A {H.new 1 {H.new write 1 | move 1 | next A} | B {H.new write 1 | move 0 | next B} } } A B B} } _h3 2.3) concatening two sets of ones {pre '{tm unary_adder {A.new 1 1 1 0 1 1 1} {H.new A {H.new 1 {H.new write 0 | move 1 | next B} } | B {H.new 1 {H.new write 1 | move 1 | next B} | 0 {H.new write 1 | move 0 | next H} } } A H B} output: {tm unary_adder {A.new 1 1 1 0 1 1 1} {H.new A {H.new 1 {H.new write 0 | move 1 | next B} } | B {H.new 1 {H.new write 1 | move 1 | next B} | 0 {H.new write 1 | move 0 | next H} } } A H B} } _h3 2.4) duplicating a set of ones {pre '{tm duplicate {A.new 1 1 1} {H.new q0 {H.new 1 {H.new write B | move 1 | next q1} } | q1 {H.new 1 {H.new write 1 | move 1 | next q1} | 0 {H.new write 0 | move 1 | next q2} | B {H.new write 0 | move 1 | next q2}} | q2 {H.new 1 {H.new write 1 | move 1 | next q2} | B {H.new write 1 | move -1 | next q3}} | q3 {H.new 1 {H.new write 1 | move -1 | next q3} | 0 {H.new write 0 | move -1 | next q3} | B {H.new write 1 | move 1 | next q4}} | q4 {H.new 1 {H.new write B | move 1 | next q1} | 0 {H.new write 0 | move 1 | next qf}} } q0 qf B} output: {tm duplicate {A.new 1 1 1} {H.new q0 {H.new 1 {H.new write B | move 1 | next q1} } | q1 {H.new 1 {H.new write 1 | move 1 | next q1} | 0 {H.new write 0 | move 1 | next q2} | B {H.new write 0 | move 1 | next q2}} | q2 {H.new 1 {H.new write 1 | move 1 | next q2} | B {H.new write 1 | move -1 | next q3}} | q3 {H.new 1 {H.new write 1 | move -1 | next q3} | 0 {H.new write 0 | move -1 | next q3} | B {H.new write 1 | move 1 | next q4}} | q4 {H.new 1 {H.new write B | move 1 | next q1} | 0 {H.new write 0 | move 1 | next qf}} } q0 qf B} } _h3 2.5) sorting numbers {pre '{tm sort {A.new 2 1 2 2 2 1 1} {H.new A {H.new 1 {H.new write 1 | move 1 | next A} | 2 {H.new write 3 | move 1 | next B} | 0 {H.new write 0 | move -1 | next E}} | B {H.new 1 {H.new write 1 | move 1 | next B} | 2 {H.new write 2 | move 1 | next B} | 0 {H.new write 0 | move -1 | next C}} | C {H.new 1 {H.new write 2 | move -1 | next D} | 2 {H.new write 2 | move -1 | next C} | 3 {H.new write 2 | move -1 | next E}} | D {H.new 1 {H.new write 1 | move -1 | next D} | 2 {H.new write 2 | move -1 | next D} | 3 {H.new write 1 | move 1 | next A}} | E {H.new 1 {H.new write 1 | move -1 | next E} | 0 {H.new write 0 | move 1 | next H}} } A H 0} output: {tm sort {A.new 2 1 2 2 2 1 1} {H.new A {H.new 1 {H.new write 1 | move 1 | next A} | 2 {H.new write 3 | move 1 | next B} | 0 {H.new write 0 | move -1 | next E}} | B {H.new 1 {H.new write 1 | move 1 | next B} | 2 {H.new write 2 | move 1 | next B} | 0 {H.new write 0 | move -1 | next C}} | C {H.new 1 {H.new write 2 | move -1 | next D} | 2 {H.new write 2 | move -1 | next C} | 3 {H.new write 2 | move -1 | next E}} | D {H.new 1 {H.new write 1 | move -1 | next D} | 2 {H.new write 2 | move -1 | next D} | 3 {H.new write 1 | move 1 | next A}} | E {H.new 1 {H.new write 1 | move -1 | next E} | 0 {H.new write 0 | move 1 | next H}} } A H 0} } _h3 2.6) filling an empty array with ones, short version _p See [[busy_beaver|https://en.wikipedia.org/wiki/Busy_beaver]]. {pre '{tm busy_beaver {A.new} {H.new A {H.new 0 {H.new write 1 | move 1 | next B} | 1 {H.new write 1 | move -1 | next C}} | B {H.new 0 {H.new write 1 | move -1 | next A} | 1 {H.new write 1 | move 1 | next B}} | C {H.new 0 {H.new write 1 | move -1 | next B} | 1 {H.new write 1 | move 0 | next H}} } A H 0} output: {tm busy_beaver {A.new} {H.new A {H.new 0 {H.new write 1 | move 1 | next B} | 1 {H.new write 1 | move -1 | next C}} | B {H.new 0 {H.new write 1 | move -1 | next A} | 1 {H.new write 1 | move 1 | next B}} | C {H.new 0 {H.new write 1 | move -1 | next B} | 1 {H.new write 1 | move 0 | next H}} } A H 0} } _h3 2.7) filling an empty array with ones, long version _p This machine runs for more than 47 millions steps, we just stop it at 100... {pre '{tm busy_beaver2 {A.new} {H.new A {H.new 0 {H.new write 1 | move 1 | next B} | 1 {H.new write 1 | move -1 | next C}} | B {H.new 0 {H.new write 1 | move 1 | next C} | 1 {H.new write 1 | move 1 | next B}} | C {H.new 0 {H.new write 1 | move 1 | next D} | 1 {H.new write 0 | move -1 | next E}} | D {H.new 0 {H.new write 1 | move -1 | next A} | 1 {H.new write 1 | move -1 | next D}} | E {H.new 0 {H.new write 1 | move 0 | next K} | 1 {H.new write 0 | move -1 | next A}} } A K 0} output: {tm busy_beaver2 {A.new} {H.new A {H.new 0 {H.new write 1 | move 1 | next B} | 1 {H.new write 1 | move -1 | next C}} | B {H.new 0 {H.new write 1 | move 1 | next C} | 1 {H.new write 1 | move 1 | next B}} | C {H.new 0 {H.new write 1 | move 1 | next D} | 1 {H.new write 0 | move -1 | next E}} | D {H.new 0 {H.new write 1 | move -1 | next A} | 1 {H.new write 1 | move -1 | next D}} | E {H.new 0 {H.new write 1 | move 0 | next K} | 1 {H.new write 0 | move -1 | next A}} } A K 0} } _p ... and so on, theoretically anything. {center The lambda calculus and the Universal Turing Machines are equivalent.} _p {i Alain Marty | 2020/10/21} {style pre {box-shadow:0 0 8px; padding:5px; } } {script (function() { var HASH = {}, HASH_num = 0; LAMBDATALK.DICT["H.lib"] = function() { var str = "", index = 0; for (var key in LAMBDATALK.DICT) { if (LAMBDATALK.DICT.hasOwnProperty(key) && key.substring(0,2) === "H.") { str += key + ", "; index++; } } return "HASH: [" + index + "] [" + str.substring(0, str.length - 2) + "]"; }; LAMBDATALK.DICT["H.new"] = function() { var args = LAMBDATALK.supertrim(arguments[0]).split('|'); var hash = {}; for (var i=0; i < args.length; i++) { var keyval = args[i].trim().split(' '); var key = keyval.shift(); hash[key] = keyval.join(' '); } var name = '_HASH_' + HASH_num++; HASH[name] = hash; return name; }; LAMBDATALK.DICT["H.disp"] = function() { // {H.disp hash} var args = LAMBDATALK.supertrim(arguments[0]); // JSON.stringify( HASH[args] ); // return "[" + hash.substring(1,hash.length-1) + "]"; var hash = HASH[args]; var s="\n[\n"; for (key in hash) s += key + ": " + hash[key] + "\n"; return s + "\]" }; LAMBDATALK.DICT["H.get"] = function() { // {H.get hash key} var args = LAMBDATALK.supertrim(arguments[0]).split(' '); var hash = HASH[args[0]]; var key = args[1]; return hash[key] }; LAMBDATALK.DICT["H.set!"] = function() { // {H.set! hash key val} var args = LAMBDATALK.supertrim(arguments[0]).split(' '); var hash = args.shift(); var key = args.shift(); var val = args.join(" "); HASH[hash][key] = val; return hash; }; })(); }
lambdaway v.20211111