Computation theory question

This is a discussion on Computation theory question within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Why do I feel like for the past week and a half Clyde has been sitting in front of a ...

  1. #16
    The Earth is not flat. Clyde's Avatar
    Join Date
    Mar 2002
    Posts
    1,420
    Why do I feel like for the past week and a half Clyde has been sitting in front of a homework paper with a check box for "Yes" and one for "No" waiting for a straight answer?
    I'm way past homework . The question was actually motivated by reading neuroscience stuff.

    So the answer is... anything is possible.
    And mainly this is so because... turing machines don't exist.
    Really? I thought computers used the Von Neuman architecture and the Von Neuman architecture was a way of making a universal turing machine. I thought my PC was a universal Turing machine. I've made a mistake?
    Entia non sunt multiplicanda praeter necessitatem

  2. #17
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,460
    Yup. You've made a mistake. Your computer is not a Turing Machine, much less an UTM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  3. #18
    Registered User
    Join Date
    Aug 2005
    Posts
    44
    Wouldnt the Altair computer be a better test for binary calculations that a Turing machine? You can download simulators of the Altair at sites like this:
    http://incolor.inetnebr.com/bill_r/c...simulators.htm

    I really dont understand the significance of the Turing machine in computer theory, it uses symbols instead of zeros and ones, so what is to limit the complexity of the alphabet in this set of symbols?

  4. #19
    The Earth is not flat. Clyde's Avatar
    Join Date
    Mar 2002
    Posts
    1,420
    Yup. You've made a mistake. Your computer is not a Turing Machine, much less an UTM.
    Cool, thanks for the link, now i must discover why this:

    The difference lies only with the ability of a Turing machine to manipulate an unbounded amount of data. However, given a finite amount of time, a Turing machine (like a real machine) can only manipulate a finite amount of data.
    leads to this:

    One way in which Turing machines are a poor model for programs is that many real programs, such as operating systems and word processors, are written to receive unbounded input over time, and therefore do not halt. Turing machines do not model such ongoing computation well (but can still model portions of it, such as individual procedures).
    I'm not sure it really alters the natyre of my question, - which is basically given all the physical information is it always feasible to unravel the underlying logic. Never the less i am gratefull for the clarification.
    Entia non sunt multiplicanda praeter necessitatem

  5. #20
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,460
    It may look like a contradiction at first. However, the answer lies a few paragraphs before.

    Arguably this is an hard concept to understand, since our brain cannot model very well the workings of a Turing machine. Only maths can model it. This is ironic because our brain is probably the only turing machine currently in existence in the world. However, I belive the key in understanding TMs and the answer to that apparent contradiction you explored is that TMs, contrary to any man-made machine to date, are not finit deterministic machines.

    In the world of machines to this date, given a current state and a condition, you can only have one transition state. We observe this behavior in the real world out there; A door is closed. If we open it we set an open state. And if we close it we set a close state. We can at best formulate from this state machine and expand it using other state processes. If the door is open a draft state is set. If it is closed the draft state is cancelled. However each transition state table is a contained finit and deterministic unit. Computers simply cannot process infinit non-deterministic states. That's what intelligence does.

    The maths behind the description of finit state machines and turing machines are well beyond my capabilities. However, the resulting concept is more or less the above.

    A turing machine is not necessarily a sentient being though. It is simply an hypothesis of a machine that can process infinit and non-deterministic states. A turing machine would probably, for instance, be able to produce random numbers much the same way we humans do, however it would be incapable of using that information for anything more than what it was programmed to do.

    We can simulate turing machines by tricking our computers (and our brains) into thinking we are working with an infinit non-deterministic set of information and states. However, it's all hocus pocus. As the random tables in any computer are. Just a trick to simulate.

    We cannot build turing machines... yet.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  6. #21
    The Earth is not flat. Clyde's Avatar
    Join Date
    Mar 2002
    Posts
    1,420
    Computers simply cannot process infinit non-deterministic states. That's what intelligence does.
    Hmm i must confess that I don't think intelligence processes an infinite number of states - presumably a neuron can only be a finite (though possibly absurdly large) number of states.

    It is simply an hypothesis of a machine that can process infinit and non-deterministic states.
    I understand why you refer to the infinite part bit but i'm pretty sure there are both deterministic and non-deterministic turing machines. Which checking wiki seems to be right:

    http://en.wikipedia.org/wiki/Turing_...uring_machines

    So i'm not so sure whether the non-determinsitic part is necessarily the important bit.

    Thanks for explaining your view though.
    Entia non sunt multiplicanda praeter necessitatem

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. another do while question
    By kbpsu in forum C++ Programming
    Replies: 3
    Last Post: 03-23-2009, 12:14 PM
  2. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  3. opengl DC question
    By SAMSAM in forum Game Programming
    Replies: 6
    Last Post: 02-26-2003, 08:22 PM
  4. Theory question...
    By Imperito in forum C++ Programming
    Replies: 1
    Last Post: 01-01-2003, 04:58 AM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 12:47 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21