> On 20 Jul 2019, at 16:40, John Clark <[email protected]> wrote: > > On Sat, Jul 20, 2019 at 5:21 AM Telmo Menezes <[email protected] > <mailto:[email protected]>> wrote: > > >> X is a Turing Machine if and only if for any given input to X there exists > >> a Turing Machine that will produce the same output as X does with the same > >> input. > > > Ok, but then you can replace "Turing Machine" above with "von Neumann > > Machine" or "GPU" and it still works. > > You could if you wanted to because unlike Lambda calculus Turing Machines, > von Neumann Machines, and GPUs can all be implemented physically; but if > you're only interested in philosophy then you wouldn't want to because you > would just be inserting in tons of additional engineering details needed to > make computers economically viable. > > Only?! If X is Turing Complete then a Turing Machine can emulate X and X can > emulate a Turing Machine. > > > Yes, but the Turing Machine has no special status in relation to any other > > Turing complete system. > > It is the simplest Turing complete system. > > >> Do you know of anything simpler that can make calculations than read a > >> square, erase what you read and then print either a 0 or a 1 on it > >> depending on your state, then change into another state depending on what > >> you read, then either halt or move right or left and read another square. > > > Simple in what sense? > > The amount of information needed to describe its most basic operation. > > > I can think of physical implementations of computers that simpler in the > > sense that they do not require some sort of writing device, > > Any computer is going to need memory to store the program and usually there > will be data too, and memory involves reading and writing. > > > motors to move the tape, > > Any computer with more than one bit of memory is going to need to move the > place where it reads and writes. > > > some sort of sensor to read the state, > > Any computer is going to have to have internal states that change, and that > change can't be random, the change must depend on its current state and the > next bit of information it reads. > > > then some mechanism to make the decision on how to activate the motors and > > writing device. I gave you one: Domino. It only requires objects falling > > over other objects. Or the billiard ball computer, which only requires the > > physical collision of balls inside tubes. > > The position of the billiard balls are the memory and determine the state of > the machine, however the 2D position of a billiard ball can't be described by > just one bit of information as a square on Turing's tape can be. So a 2D > billiard ball computer is considerably more complicated than a 1D paper tape, > but if you like the billiard balls that's fine because unlike Lambda Calculus > it can be implemented physically. > > > I'm sure it is possible to create computational surfaces made of lattices > > of very simple molecules. > > I'm sure of that too but there is nothing simple about molecules or the 2D > surface of 3D lattices > > > The Turing Machine is not the simplest implementation of a physical > > computer, > > You haven't told me about a simpler one.
I did. (The combinators), but you have confuse them with words, which they are not. The theory of combinators is entirely axiomatised by The 2 axioms: 1) Kxy = x 2) Sxyz = xz(yz) And the 3 rules 3) If x = y and x = z, then y = z 4) If x = y then xz = yz 5) If x = y then zx = zy You should be able to see that SKKx = x whatever combinator x represents. SKKx = Kx(Kx) by 2) Kx(Kx) = x by 1) SKK compute the identity function. See the combinator thread where I have proved the Turing universality. Or ask for more. A precise logical specification of the Turing machine is much more complex. Bruno > > > it is (perhaps?) the simplest implementation that uses explicit memory and > > sequential computations. > > If it has no memory and can't make sequential computations then you might > have a calculator but you don't have a computer. > > > These two things make it easier for us to reason about its computations, > > and that is all. It is not the "fundamental" computer. > > If its the easiest for us to understand then it is the simplest, if it can't > be made any simpler, any more elementary, without loosing important > properties then it is fundamental because that's what the word means. > > John K Clark > > > -- > You received this message because you are subscribed to the Google Groups > "Everything List" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected] > <mailto:[email protected]>. > To view this discussion on the web visit > https://groups.google.com/d/msgid/everything-list/CAJPayv0PqqyFTnTt00%2B%2BgEcCqcYN893ac1RZi%3Dnq5pQbzN7LgA%40mail.gmail.com > > <https://groups.google.com/d/msgid/everything-list/CAJPayv0PqqyFTnTt00%2B%2BgEcCqcYN893ac1RZi%3Dnq5pQbzN7LgA%40mail.gmail.com?utm_medium=email&utm_source=footer>. -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/10637641-E028-46D7-9202-2E247F034470%40ulb.ac.be.
