q%2d, p%2d %s st sym ([ for i in 0..10 -&gt aux sym i (rib i) ] Проделанное упражнение доказывает, что любая вычислимая по Тьюрингу функция вычислима в


Чтобы посмотреть презентацию с картинками, оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов презентации:

Факультет инноваций и высоких технологийМосковский физико-технический институт Лекция 20 Пример: реализация машины Тьюринга Реализуем Машину Тьюринга на функциональном языкеMT = , гдеA - алфавит (мы предполагаем char)S - множество состояний (int)L – полубесконечная лента с текущей ячейкой (n(int→A))s0S – начальное состояние (0)P – программа, состоящая из s,c – состояние + видимый символ, определяет выполняемую командуc‘ – новый символ, записываемый вместо старогоs‘ – новое состояние, в которое переходит машинаa – действие (L,R – сдвиг влево-вправо; U – на месте; H-останов) type state = int*int;; type base = char;; type ribbon = int -> base;; type op = L | R | U | H;; type instr = state * base * base * state * op;; type program = instr list;; type MT = program * state * ribbon;; let step (P,(sym,st),rib) = let s = rib sym in let (_,_,nchr,nst,cmd) = List.find(fun (q,c,_,_,_) -> (q=st)&&(c=s)) P in let nsym = proc sym cmd in (P,(nsym,nst),ins nchr sym rib);; let proc n = function R -> n+1 | L -> n-1 | U -> n | H -> -1;; let ins c n rib = fun x -> if n=x then c else rib x;; let empty = fun x -> ' ';; let terminal MT = match MT with (_,(n,_),_) when n<0 -> true | _ -> false;; let rec run MT = if terminal MT then MT else let n = step MT in let _ = print n in run (n);; let print (P,(sym,st),rib) = let aux n i (c:char) = if i=n then "["+c.ToString()+"]" else c.ToString() in printfn "q=%2d, p=%2d %s" st sym ([ for i in 0..10 -> aux sym i (rib i) ] |> List.fold_left(fun ac c -> ac+c) "");; let mkrib (s:string) = let rec f n = function [] -> empty | h::t -> ins h n (f (n+1) t) in s.ToCharArray() |> List.of_array |> (f 0);; Проделанное упражнение доказывает, что любая вычислимая по Тьюрингу функция вычислима в λ-исчисленииПоскольку мы нигде не использовали конечность ленты В приведенной реализации по ходу выполнения растет сложность доступа к лентеВозможно использование более эффективных структур:Массив с произвольным доступом (F#)ДеревоЗиппер (2 списка – левая и правая полулента) type 'a zipper = 'a list * 'a list;; let left (l,r) = match l with [] -> ([],' '::r) | x::t -> (t,x::r);; let right (l,r) = match r with [] -> (' '::l,[]) | x::t -> (x::l,t);; let norm (l,r) = match r with [] -> (l,[' ']) | _ -> (l,r);; A B C D E F … ([’C’;’B’;’A’],[’D’;’E’;’F’]) let step (P,st,rib) = let (l,x::r) = norm rib in let (_,_,nchr,nst,cmd) = List.find(fun (q,c,_,_,_) -> (q=st)&&(c=x)) P in let nrib = proc (l,nchr::r) cmd in (P,nst,nrib);; let proc n = function R -> right n | L -> left n | U -> n | H -> ([],[]) ;; Для функционального программирования характерны специфические структуры данныхИз-за отсутствия памяти с «прямым» доступомИз-за того, что в идеале все структуры immutableОкасаки, Purely Functional Data Structures

Приложенные файлы

  • ppt 7077592
    Размер файла: 3 MB Загрузок: 0

Добавить комментарий