Ejemplos de Maquina de Turing
NUMERO BINARIO DIVISIBLE POR 3
// Input: a binary number n
// Ouput: accepts if n mod 3 == 0
// Example: accepts 110 (=6)
//
// Divisible by 3 Algorithm
// for Turing Machine Simulator
// turingmachinesimulator.com
//
// ------- States -----------|
// q0 - mod3 == 0 |
// q1 - mod3 == 1 |
// q2 - mod3 == 2 |
// qaccept - accepting state |
//---------------------------|
name: Binary numbers divisible by 3
init: q0
accept: qAccept
q0,0
q0,0,>
q0,1
q1,1,>
q1,0
q2,0,>
q1,1
q0,1,>
q2,0
q1,0,>
q2,1
q2,1,>
q0,_
qAccept,_,-
DECIMAL A BINARIO
//////////////////////
// turing: dec to bin
//////////////////////
// Copyright (c) 2013 Max von Buelow
// Copyright (c) 2013 kd3x
// License: CC BY-NC-SA 3.0
// Simulator: turingmachinesimulator.com
// Initial state: qinit
// Accepting state: qfin
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// Greetings to the course 'FGdI 1'
// at the TU Darmstadt.
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
name: Decimal to binary
init: qinit
accept: qfin
qinit,0
qinit,0,>
qinit,1
qinit,1,>
qinit,2
qinit,2,>
qinit,3
qinit,3,>
qinit,4
qinit,4,>
qinit,5
qinit,5,>
qinit,6
qinit,6,>
qinit,7
qinit,7,>
qinit,8
qinit,8,>
qinit,9
qinit,9,>
qinit,_
halve,0,<
// Halve and go to addHalf to add the goBack
halve,0
halve,0,<
halve,1
addHalf,0,>
halve,2
halve,1,<
halve,3
addHalf,1,>
halve,4
halve,2,<
halve,5
addHalf,2,>
halve,6
halve,3,<
halve,7
addHalf,3,>
halve,8
halve,4,<
halve,9
addHalf,4,>
// Add 0.5 to the right
addHalf,0
jump,5,<
addHalf,1
jump,6,<
addHalf,2
jump,7,<
addHalf,3
jump,8,<
addHalf,4
jump,9,<
// Jump back
jump,0
halve,0,<
jump,1
halve,1,<
jump,2
halve,2,<
jump,3
halve,3,<
jump,4
halve,4,<
// If we halved successfully, we first remove the zero if there is one and then we go back
halve,_
removezero,_,>
removezero,0
removezero,_,>
removezero,1
goBack,1,>
removezero,2
goBack,2,>
removezero,3
goBack,3,>
removezero,4
goBack,4,>
removezero,5
goBack,5,>
removezero,6
goBack,6,>
removezero,7
goBack,7,>
removezero,8
goBack,8,>
removezero,9
goBack,9,>
// qfinished
removezero,_
qfin,_,>
// normal goBack
goBack,0
goBack,0,>
goBack,1
goBack,1,>
goBack,2
goBack,2,>
goBack,3
goBack,3,>
goBack,4
goBack,4,>
goBack,5
goBack,5,>
goBack,6
goBack,6,>
goBack,7
goBack,7,>
goBack,8
goBack,8,>
goBack,9
goBack,9,>
// rest
goBack,_
rest,_,<
rest,0
rest0,_,>
rest0,_
setrest0,_,>
rest,5
rest1,_,>
rest1,_
setrest1,_,>
setrest0,0
setrest0,0,>
setrest0,1
setrest0,1,>
setrest1,0
setrest1,0,>
setrest1,1
setrest1,1,>
setrest0,_
continue,0,<
setrest1,_
continue,1,<
// continue
continue,0
continue,0,<
continue,1
continue,1,<
continue,_
continue2,_,<
// delimiter
continue2,_
halve,0,<
CANTIDAD PAR DE CEROS
// Input: a binary number n// Ouput: accepts if n has// an even amount of 0s// Example: accepts 100100//// Even Amount of 0s Algorithm// for Turing Machine Simulator// turingmachinesimulator.com//// --------- States -----------|// q0 amount of 0s mod2 == 0 |// q1 amount of 0s mod2 == 1 |// qAccept - accepting state |//-----------------------------|name: Even amount of zerosinit: q0accept: qAcceptq0,0q1,0,>q1,0q0,0,>q0,1q0,1,>q1,1q1,1,>q0,_qAccept,_,-
PALINDROMO BINARIO
//////////////////////
// turing: dec to bin
//////////////////////
// Copyright (c) 2013 Max von Buelow
// Copyright (c) 2013 kd3x
// License: CC BY-NC-SA 3.0
// Simulator: turingmachinesimulator.com
// Initial state: qinit
// Accepting state: qfin
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// Greetings to the course 'FGdI 1'
// at the TU Darmstadt.
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
name: Decimal to binary
init: qinit
accept: qfin
qinit,0
qinit,0,>
qinit,1
qinit,1,>
qinit,2
qinit,2,>
qinit,3
qinit,3,>
qinit,4
qinit,4,>
qinit,5
qinit,5,>
qinit,6
qinit,6,>
qinit,7
qinit,7,>
qinit,8
qinit,8,>
qinit,9
qinit,9,>
qinit,_
halve,0,<
// Halve and go to addHalf to add the goBack
halve,0
halve,0,<
halve,1
addHalf,0,>
halve,2
halve,1,<
halve,3
addHalf,1,>
halve,4
halve,2,<
halve,5
addHalf,2,>
halve,6
halve,3,<
halve,7
addHalf,3,>
halve,8
halve,4,<
halve,9
addHalf,4,>
// Add 0.5 to the right
addHalf,0
jump,5,<
addHalf,1
jump,6,<
addHalf,2
jump,7,<
addHalf,3
jump,8,<
addHalf,4
jump,9,<
// Jump back
jump,0
halve,0,<
jump,1
halve,1,<
jump,2
halve,2,<
jump,3
halve,3,<
jump,4
halve,4,<
// If we halved successfully, we first remove the zero if there is one and then we go back
halve,_
removezero,_,>
removezero,0
removezero,_,>
removezero,1
goBack,1,>
removezero,2
goBack,2,>
removezero,3
goBack,3,>
removezero,4
goBack,4,>
removezero,5
goBack,5,>
removezero,6
goBack,6,>
removezero,7
goBack,7,>
removezero,8
goBack,8,>
removezero,9
goBack,9,>
// qfinished
removezero,_
qfin,_,>
// normal goBack
goBack,0
goBack,0,>
goBack,1
goBack,1,>
goBack,2
goBack,2,>
goBack,3
goBack,3,>
goBack,4
goBack,4,>
goBack,5
goBack,5,>
goBack,6
goBack,6,>
goBack,7
goBack,7,>
goBack,8
goBack,8,>
goBack,9
goBack,9,>
// rest
goBack,_
rest,_,<
rest,0
rest0,_,>
rest0,_
setrest0,_,>
rest,5
rest1,_,>
rest1,_
setrest1,_,>
setrest0,0
setrest0,0,>
setrest0,1
setrest0,1,>
setrest1,0
setrest1,0,>
setrest1,1
setrest1,1,>
setrest0,_
continue,0,<
setrest1,_
continue,1,<
// continue
continue,0
continue,0,<
continue,1
continue,1,<
continue,_
continue2,_,<
// delimiter
continue2,_
halve,0,<
DECIMAL A BINARIO
// Input: a binary number n
// Ouput: accepts if n is a palindrome
// Example: accepts 10101
//
// Palindrome Algorithm
// for Turing Machine Simulator
// turingmachinesimulator.com
name: Binary palindrome
init: q0
accept: qAccept
q0,0
qRight0,_,>
qRight0,0
qRight0,0,>
qRight0,1
qRight0,1,>
q0,1
qRight1,_,>
qRight1,0
qRight1,0,>
qRight1,1
qRight1,1,>
qRight0,_
qSearch0L,_,<
qSearch0L,0
q1,_,<
qRight1,_
qSearch1L,_,<
qSearch1L,1
q1,_,<
q1,0
qLeft0,_,<
qLeft0,0
qLeft0,0,<
qLeft0,1
qLeft0,1,<
q1,1
qLeft1,_,<
qLeft1,0
qLeft1,0,<
qLeft1,1
qLeft1,1,<
qLeft0,_
qSearch0R,_,>
qSearch0R,0
q0,_,>
qLeft1,_
qSearch1R,_,>
qSearch1R,1
q0,_,>
qSearch0R,1
qReject,1,-
qSearch1R,0
qReject,0,-
qSearch0L,1
qReject,1,-
qSearch1L,0
qReject,0,-
q0,_
qAccept,_,-
q1,_
qAccept,_,-
qSearch0L,_
qAccept,_,-
qSearch0R,_
qAccept,_,-
qSearch1L,_
qAccept,_,-
qSearch1R,_
qAccept,_,-
Comentarios
Publicar un comentario