Por favor explique esta definición formal de computación

7

Estoy tratando de atacar a TAOCP una vez más, dada la gran pesadez literal de los volúmenes que tengo problemas para comprometerme en serio. En TAOCP 1 Knuth escribe, página 8, conceptos básicos ::

Dejar Aser un conjunto finito de letras. DejarA ser el conjunto de todas las cadenas en A (el conjunto de todas las secuencias ordenadas x1 x2 ... xn dónde n0 y xj es en A para 1jn) La idea es codificar los estados del cálculo para que estén representados por cadenas deA. Ahora dejaN ser un número entero no negativo y Q (el estado) sea el conjunto de todos (σ,j), dónde σ es en A y j es un entero 0jN; dejarI (la entrada) sea el subconjunto de Q con j=0 y deja Ω (la salida) sea el subconjunto con j=N. Siθ y σ son cadenas en A, Nosotros decimos eso θ ocurre en σ Si σ tiene la forma αθω para cuerdas α y ω. Para completar nuestra definición, dejemosf ser una función del siguiente tipo, definido por las cadenas θj, ϕj y los enteros aj, bj para 0jN:

  • f((σ,j))=(σ,aj) Si θj no ocurre en σ
  • f((σ,j))=(αψjω,bj) Si α es la cadena más corta posible para la cual σ=αθjω
  • f((σ,N))=(σ,N)

Al no ser un informático, tengo problemas para comprender todo el pasaje. Tengo la idea de que está detrás de un sistema de códigos de operación, pero no he progresado efectivamente en la comprensión. Creo que el problema principal es tat. No sé cómo leerlo de manera efectiva.

¿Sería posible explicar el pasaje anterior para que pueda entenderlo y darme una estrategia para entrar en la lógica al interpretar estas declaraciones?

Stefano Borini
fuente
Entonces no debe incluir su comentario en la supuesta cita, confundiendo a cualquiera que no tenga el libro a mano. -.- Espero que mi respuesta ayude ...
Raphael
@Raphael: la cita es literal del libro. Acabo de agregar una explicación entre paréntesis de los símbolos para I y omega
Stefano Borini
@SteanoBorini: Pero no es una "explicación", está mal. Veo cómo puedes leer el texto original para llegar a la misma conclusión que lo hiciste, pero todavía no es útil. Si dice que cita algo y agrega comentarios, márquelo como tal para que las personas puedan tomarlo con un grano de sal.
Raphael
Aquí falta un contexto: ¿qué cálculo y qué estados?
reinierpost

Respuestas:

8

Nos falta algo de contexto, así que no tengo idea de qué punto está tratando de hacer Knuth, pero aquí está cómo interpretar una máquina Turing de esta manera. Quizás te ayudará a entender lo que está sucediendo. En general, una buena forma de controlar un concepto es jugar con él. En el caso de paradigmas de programación, eso significa escribir un programa. En este caso, mostraré cómo escribir cualquier programa.

Supongamos que la cinta de la máquina Turing tiene símbolos {0,1,ϵ} (dónde ϵ significa "vacío") y agregue un símbolo más que represente la ubicación de la cabeza H. Tus estados van a ser pares de la forma(q,α), dónde q es un estado de la máquina de Turing, y α{0,,14}. También identificamos(F,0) con N para cualquier estado final.

Entrada activada (no vacía) x, tu punto de partida será (Hx,(s,0)), dónde s is the starting state. The difficult part is to encode states. Suppose that at state q, upon reading input x, you replace it with a(q,x), move in direction D(q,x){L,R}, and switch to state σ(q,x). For the θs, we have

θq,0=0H0,θq,1=0H1,θq,2=0Hϵ,θq,3=1H0,θq,4=1H1,θq,5=1Hϵ,θq,6=ϵH0θq,7=ϵH1,θq,8=ϵHϵ,θq,9=H0,θq,10=H1,θq,11=Hϵ,θq,12=0H,θq,13=1H,θq,14=ϵH.
For the as, we have aq,i=(q,i+1) for i<14, and aq,14=(q,14), though we should never really get that far. For the bs, we have
bq,0=bq,3=bq,6=bq,9=(σ(q,0),0),bq,1=bq,4=bq,7=bq,10=(σ(q,1),0),bq,2=bq,5=bq,8=bq,11=bq,12=bq,13=bq,14=(σ(q,ϵ),0).
Now it remains to determine the ψs. Let a0=a(q,0). If D(q,0)=L then
ψq,0=H0a0,ψq,3=H1a0,ψq,6=ψq,9=Hϵa0.
If D(q,0)=R then
ψq,0=0a0H,ψq,3=1a0H,ψq,6=ϵa0H,ψq,9=a0Hϵ.
Next, let a1=a(q,1). If D(q,1)=L then
ψq,1=H0a1,ψq,4=H1a1,ψq,7=ψq,10=Hϵa1.
If D(q,1)=R then
ψq,1=0a1H,ψq,4=1a1H,ψq,7=ϵa1H,ψq,10=a1Hϵ.
Finally, let aϵ=a(q,ϵ). If D(q,ϵ)=L then
ψq,2=H0aϵ,ψq,5=H1aϵ,ψq,8=ψq,11=Hϵaϵ,ψq,12=H0aϵ,ψq,13=H1aϵ,ψq,14=Hϵaϵ.
If D(q,ϵ)=R then
ψq,2=0aϵH,ψq,5=1aϵH,ψq,8=ϵaϵH,ψq,11=aϵHϵ,ψq,12=0aϵH,ψq,13=1aϵH,ψq,14=ϵaϵH.

Now apply f repeatedly until you get stuck. If you follow the construction, you will see that we have simulated the running of the Turing machine.

Yuval Filmus
fuente
understood: nothing. Not your fault. Thank you anyway :(
3
"Nos falta algo de contexto". Es: deberíamos tener una descripción precisa de lo que queremos decir con un "método de cálculo"; aquí hay uno dado por AA Markov; Hay otros equivalentes, como las máquinas de Turing.
rgrig
6

Vamos a desglosarlo poco a poco. En primer lugar, recuerde lo que Knuth escribió en la página 7:

Definamos formalmente un método computacional para que sea cuádruple(Q,I,Ω,f), in which Q is a set containing subsets I and Ω, and f is a function from Q into itself. [...] The four quantities Q, I, Ω, f are intended to represent repectively the state of the computation, the input, the output, and the computational rule.

This is the outline. You have to read "represent" as "contain"; Q is going to contain states (some of which are in I, some are in Ω) and f is going to be a transition function between states; think of it as a program.

Let A be a finite set of letters. Let A be the set of all strings in A (the set of all ordered sequences x1 x2 ... xn where n0 and xj is in A for 1jn).

This is just a reiteration of what A is. See also here.

The idea is to encode the states of the computation so that they are represented by strings of A.

This is probably the key sentence. We are talking about computations, that is execution sequences of some (programming language) statements which manipulate some state, which can be thought of as values in memory cells, or valuations of variables. Knuth says here that he wants to encode these states in an abstract way, namely as word over some alphabet.

Example: Consider a program that uses (at most) k variables, each of which stores an integer. That is, a state is given by the tuple of values (x1,,xk) where xk is the (current) value of the k-th variable. In order to encode states of this form in a formal language, we can choose A={0,1,#} with # a separator. Now model such a state by #x1¯##xk¯# where xi¯ is the binary encoding of xi.

Specifically, (3,5,0) would be #11#101#0#.

Now let N be a non-negative integer and Q be the set of all (σ,j), where σ is in A and j is an integer 0jN; let I be the subset of Q with j=0 and let Ω be the subset with j=N.

You misquoted there (bad Stefano!); the parentheses are not in the original text, and they were misleading (see above). Knuth defines Q here as the set of all possible states (σA) at all possible places in the computation (j can be understood as program counter). Therefore, Q contains all statement-indexed states any computation of the algorithm given by f can assume. By definition, we start with program counter 0 and end in N, thus states indexed 0 are input states and those indexed N are output states.

If θ and σ are strings in A, we say that θ occurs in σ if σ has the form αθω for strings α and ω.

I hope that this is clear; it is just a (re)definition of substrings.

To complete our definition, let f be a function of the following type, defined by the strings θj, ϕj and the integers aj, bj for 0jN:

  • f((σ,j))=(σ,aj) if θj does not occur in σ
  • f((σ,j))=(αψjω,bj) if α is the shortest possible string for which σ=αθjω
  • f((σ,N))=(σ,N)

This is a a small programming language; if you fix θj,ψj,aj,bj, you have a program. On program counter j, f replaces the left-most occurrence θj in the state with ψj and goes to statement bj. If there is no θj in the current state, it goes to statement aj. The program loops if statement N is reached, modelling termination.

On the upper half of page 8, there is a more concrete example of a "program" f. Keep in mind that Knuth is going to use assembly language later on; this informs how he looks at programs (atomic statements connected by jumps).

Raphael
fuente
1
Now I got a bit better understanding of what is going on. However, two things are still not clear and I would really appreciate if you could expand your answer. First, θj,ψj,aj,bj - what are these strings and numbers? What do they represent? If I understand correctly, aj and bj represent the step number or command counter for state j+1. But I am not sure what θj,ψj strings mean. Can you explain what do you mean by " if you fix θj,ψj,aj,bj, you have a program"? Or rather, how would I fix it for some example?
Georgy Bolyuba
@GeorgyBolyuba: You are right about aj and bj. The program's state is a string σ and a "program counter" j. θj and ψj are used to modify that state (see second case of f). They can have all kinds of shapes; it really depends on how you encode state as a string. See the book for an example.
Raphael
5

That text describes the following (Python) pseudocode:

subs = a list of string pairs  
As = a list of integers  
Bs = a list of integers

def f(state, pc):  
  if pc == N: return (state, pc)  
  if state.find(subs[pc][0]) != -1:  
    return (state.replace(subs[pc][0],subs[pc][1],1), Bs[pc])  
  else:  
    return (state,As[pc])  

The function f is presumably going to be applied repeatedly.

The last three bullet points is all you really need once you understand the notations. All that comes before is a bit analogous to explaining how Python works before giving the Python code.

rgrig
fuente
Ah ok, it's a Turing machine.
Stefano Borini
1
Rather, it is a different model of computation with the same power as a Turing machine.
Yuval Filmus
Well, three lines below your quote Knuth says that this is equivalent to Turing machines, so presumably you already knew this when you asked. I thought you were asking for help with the notation. Now I have no idea what is it that you wanted to ask.
rgrig