Universal Turing machine: Difference between revisions

Line 1,311:

the-right-part)) ; i+1 i+2 i+3 ...

;; the initial record on the tape

;; The tape in initial state

(define-m initial-tape

[(cons h t) (Tape '() h t)])

Line 1,323:

;; 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

Line 1,330:

Line 1,329:

;; 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

[('() t) t]

Line 1,340:

Line 1,339:

;; A tape is shown as (... a b c (d) e f g ...)

;; where (d) marks the current position of the caret.

(define (revappend a b) (foldl cons b a))

(define-m show-tape

[(Tape '() '() '()) '() ]

[(Tape '() '() '()) '()]

[(Tape l '() r) (revappend l (cons '() r))]

[(Tape l v r) (revappend l (cons (list v) r))])

;;;-------------------------------------------------------------------

Line 1,388:

Line 1,389:

</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:

Line 1,432:

Line 1,433:

End (1 1 (1))

(1 1 1)

> (~~ADD1~~ ~~(ADD1~~ '(1 1 0)))

> (define ADD2 (compose ADD1 ADD1))

> (ADD2 '(1 1 0))

STATE TAPE

Start ((1) 1 0)