L2 = {<M> : M is a TM and there exists an input string w such that M halts within 10 steps on input w}Hola. Estoy creando un algoritmo para demostrar por encima de L2 es decidible. Y la pista se da como sigue:
Para demostrar que L2 es decidible, pruebe un TM M dado en todos los de longitud máxima 10, cada una durante 10 pasos. Tenga en cuenta que hay finitamente finitas, por lo que este algoritmo siempre terminará. Si M se detiene en cualquier cadena de entrada w en 10 pasos, entonces w' es el prefijo de prefijo de w de longitud 10. M también se detendrá en la entrada w' en 10 pasos, por lo que el algoritmo de decisión descrito anteriormente lo encontrará.
No puedo entender esta insinuación.
M(w)
let w be w1,w2,... such that w=w1,w2,...,wn
for i=1,2,...,10
run m on wi for 10 steps
if it accepts
let w' be prefix of w of length 10 and w' be w1,w2,... such that w'=w'1,w'2,...,w'n
for t=1,2,...,10
run m on w't for 10 steps
end for
end if
end for
end M(W) Como se puede ver por encima de algoritmo que hice, no tengo ni idea de hacer algoritmo adecuado de los L2 defnition y sugerencia anterior.
Necesito ayuda para escribirlo correctamente (por favor, utiliza tu estilo para escribir un algoritmo. Creo que el estilo no importa si la idea principal es correcta. Lo que no entiendo es su idea).
Muchas gracias si me pueden ayudar.
