¿Qué significa realmente el concepto de computación?

Question

Mi pregunta es muy general, y el tipo de respuesta que busco sería tan bajo nivel como podría ser. Creo que puede ilustrar mi consulta más claramente con un ejemplo.

En lógica proposicional, usted tiene el modus ponens de la regla que lleva dos hipótesis y afirma una conclusión. La hipótesis se declaró como "estática" piezas de código, son apenas expresiones, como los axiomas de la teoría; lo mismo se aplica a la (separado) afirmación. Y por último, la regla en sí misma es también una pieza de código y "estática", en el sentido de que vagamente se indicó anteriormente. En esencia, un cálculo utilizando el modus ponens regla se desarrolla de esta manera:

$\text{1) First Hypothesis: }\vdash {P}\ \\\text{2) Second Hypothesis: } \vdash P \rightarrow Q \\ \text{3) Rule Modus Ponens: }\vdash \{ \vdash P\vdash P\rightarrow Q \vdash Q\}\\ \text{4) Assertion: }\vdash {Q}$

En el ejemplo anterior he utilizado el torniquete símbolo para denotar la noción de "comprobable" o "dado".

A pesar de que cada paso que hace que una pieza de código, algo que podría equipararse a una cadena de bits en una memoria de cinta ("estática"), lo que claramente entre los pasos 3) y 4) la "desconexión" de la afirmación se lleva a cabo. Esta acción de separar -la computación - aparece como un irreductible "dinámica" de proceso, algo que incluso si descritas por los cuatro estática escrito pasos, constituye un concepto que no parece ser en realidad "capturado" por ellos.

La extrapolación de este tipo de excesivamente simplista ejemplo, me siento preocupado con la tarea de reconciliating tanto de las ideas de la computación-como-un-objeto (por ejemplo, como una lista de instrucciones para realizar un determinado procedimiento, es decir, un programa de ordenador) y la noción de computación-como-una-acción (la dinámica acto de producir y de escupir el de salida, a partir de los datos de entrada y las reglas de procedimiento).

Hay algo que me falta, interpretación errónea, o sencillamente erróneamente indica aquí?

Answer 1

Tal vez el problema real aquí son más profundas, y de hecho no se refieren, en particular de los ordenadores. Tener claridad acerca del tema general y más específica rompecabezas acerca de los equipos debe evaporarse.

En un papel en Mente en 1895 ("Lo que la Tortuga le dijo a Aquiles"), mucho antes de la era de las computadoras, de Lewis Carroll plantea el mismo rompecabezas. Así, supongamos que la Tortuga está dado las premisas (i) $P$ y (ii) si $P$ $Q$ , pero se niega a aceptar la conclusión de $Q$.

Intenta ayudarlo, explicando pacientemente que (iii) si $P$ e si $P$ $Q$ entonces $Q$. La Tortuga hace, "OK, si usted lo dice. Ahora me acepta (i), (ii) y (iii). Pero yo todavía no aceptan $Q$".

Bien, usted podría ofrecer a él (iv) si $P$, y si $P$$Q$, y si $P$ e si $P$$Q$$Q$, a continuación, $Q$. La Tortuga, una cooperativa con los compañeros, dice que "puede Que tengas razón. OK, yo confío en usted. Voy a aceptar premisa (iv). Ahora tengo cuatro premisas. Pero lo que me obliga a aceptar $Q$?"

Se puede ver que la Tortuga otra premisa no va a ayudar!

¿Qué es la moral? Podríamos ponerlo de esta manera: la aceptación de una regla de inferencia como el modus ponens no debe confundirse con la aceptación de que una proposición como (iii). O podemos decirlo de esta manera (como Gilbert Ryle hizo en un famoso artículo en Saber Cómo y Saber Que en 1948): el conocimiento de una regla de inferencia es una cuestión de saber cómo inferir correctamente, y eso es saber cómo hacer algo, que es diferente de saber que algo es el caso, por ejemplo, a sabiendas de que (i) y (ii) o (iii) son verdaderas.

No todo el conocimiento está directamente conocimiento proposicional; algunos, como podríamos decir ahora, conocimiento procedimental, el conocimiento acerca de qué hacer. Como en el caso de la pobre Tortuga muestra, obteniendo más conocimiento proposicional no en sí mismo, dará conocimiento acerca de qué hacer. Y lo que va de Tortugas marinas se va para los equipos. Dando el equipo más datos no es lo mismo que enseñar a hacer cosas con los datos. La alimentación es la información que $P$ y que si P entonces Q es una cosa; la enseñanza a extraer inferencias en algo más. (Por eso el uso del torniquete de la notación en la configuración del problema, tanto para las afirmaciones de los datos y la especificación de una regla de inferencia es tan terriblemente engañosa.)

Answer 2

Esto es un poco sacado de la manga, así que espero que no se llega a tambalearse.

El primer paso de la definición de la computación es la de fijar un modelo. Esto es esencialmente lo que la Iglesia y de Turing se hizo con el $\lambda$-cálculo y Máquinas de Turing, respectivamente. De ser cierto sabor de equipo científico, que tienden a pensar en términos de Máquinas de Turing, así que voy a hacer referencia a ellos, pero realmente se puede pegarse a cualquier modelo de cálculo (y no hay necesidad de palo tesis de Church-Turing, en particular, es decir, no necesitamos en este momento para saber lo que realmente abarca todas cálculo, sólo que hay algo que lo hace).

Una Máquina de Turing (mt) es una colección de estados de transición de la función que describe lo que ocurre cuando ciertos entrada se encuentra en cada estado. Puede o no puede parar, no puede ser determinista o no etc. Ahora creo que el punto clave es que la TM es en sí mismo el cálculo. La descripción de lo que el TM no no lo es, es simplemente una descripción.

Esto se relaciona con un ordenador y un programa, el equipo es de (aproximadamente) un universal TM, el programa, donde es capaz de ejecutar sin que el equipo sería una TM, pero cuando se ejecuta en un ordenador es sólo de entrada. No es el cálculo, el cálculo es el equipo de producción de la salida de la entrada.

En sus ejemplos, la lista que dar (dependiendo de su punto de vista) es realmente una descripción de la "actual" estado de la computación en 4 puntos dados. El cálculo es el proceso que con la entrada pasa a través de los estados.

Answer 3

Me parece que su confusión es debido a no distinguir entre la ejecución (de un algoritmo) con el código (de un algoritmo).

Un objeto como "un coche" es diferente de un acto realizado por él como "conducir un coche".