Universal Turing machine: Difference between revisions
Content deleted Content added
m →{{header|Racket}}: Updated comments |
|||
Line 1,311: | Line 1,311: | ||
the-right-part)) ; i+1 i+2 i+3 ... |
the-right-part)) ; i+1 i+2 i+3 ... |
||
;; the initial record on the tape |
|||
;; The tape in initial state |
|||
(define-m initial-tape |
(define-m initial-tape |
||
[(cons h t) (Tape '() h t)]) |
[(cons h t) (Tape '() h t)]) |
||
Line 1,323: | Line 1,323: | ||
;; shift caret to the left |
;; shift caret to the left |
||
(define-m flip-tape |
(define-m flip-tape [(Tape l x r) (Tape r x l)]) |
||
[(Tape l x r) (Tape r x l)]) |
|||
(define shift-left |
(define shift-left |
||
Line 1,330: | Line 1,329: | ||
;; access to the current record on the tape |
;; access to the current record on the tape |
||
(define-m get |
(define-m get [(Tape _ v _) v]) |
||
[(Tape _ v _) v]) |
|||
;; writung to the current position on the tape |
|||
(define-m* put |
(define-m* put |
||
[('() t) t] |
[('() t) t] |
||
Line 1,340: | Line 1,339: | ||
;; A tape is shown as (... a b c (d) e f g ...) |
;; A tape is shown as (... a b c (d) e f g ...) |
||
;; where (d) marks the current position of the caret. |
;; where (d) marks the current position of the caret. |
||
(define (revappend a b) (foldl cons b a)) |
(define (revappend a b) (foldl cons b a)) |
||
(define-m show-tape |
(define-m show-tape |
||
[(Tape '() '() '()) '() |
[(Tape '() '() '()) '()] |
||
[(Tape l '() r) (revappend l (cons '() r))] |
[(Tape l '() r) (revappend l (cons '() r))] |
||
[(Tape l v r) (revappend l (cons (list v) r))]) |
[(Tape l v r) (revappend l (cons (list v) r))]) |
||
;;;------------------------------------------------------------------- |
;;;------------------------------------------------------------------- |
||
Line 1,388: | Line 1,389: | ||
</lang> |
</lang> |
||
The resulting Turing Machine is a function that maps the initial tape record to the final one, so that several machines could run one after another |
The resulting Turing Machine is a function that maps the initial tape record to the final one, so that several machines could run one after another or composed as any other functions |
||
Examples: |
Examples: |
||
Line 1,432: | Line 1,433: | ||
End (1 1 (1)) |
End (1 1 (1)) |
||
(1 1 1) |
(1 1 1) |
||
> ( |
> (define ADD2 (compose ADD1 ADD1)) |
||
> (ADD2 '(1 1 0)) |
|||
STATE TAPE |
STATE TAPE |
||
Start ((1) 1 0) |
Start ((1) 1 0) |