Results 1 to 2 of 2

Thread: Models of computation: from memoryless to Turing machines

  1. Top | #1
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Lebanon, OR
    Posts
    5,767
    Archived
    16,829
    Total Posts
    22,596
    Rep Power
    76

    Models of computation: from memoryless to Turing machines

    Automata theory has an nice diagram showing which of its models of computation (Model of computation) are subsets of which others.

    Combinational logic describes a memoryless system.

    Output = f(input)

    Finite-state machine or finite-state automaton is a system with an internal state register, a writable memory that contains a symbol.

    New state = f(input, old state)

    Pushdown automaton has an internal state register, and also a pushdown stack, a memory whose contents are symbols that are manipulated in Last In, First Out (LIFO) fashion.

    (New state, stack action) = f(input, old state, symbol of top of stack)
    where (stack action) is any of (do nothing), (add symbol to top of stack), (write symbol at top of stack), and (remove symbol from top of stack)

    Turing machine has an internal state register, and an infinitely-long tape memory, a memory whose contents are a string of memory cells, each one containing a symbol, and a read/write head.

    (New state, tape action) = f(input, old state, symbol in tape at head's location)
    where (tape action) is any of (do nothing), (write symbol value at head's location), (move head forward one cell), and (move head backward one cell)

    A pushdown automaton is a subset of a Turing machine.

    A sufficiently-capable Turing machine can simulate any other Turing machine, something called Turing universality. A Turing-complete system is equivalent to a universal Turing machine, though when assessing Turing completeness, finiteness is usually ignored. That aside, Turing completeness is having (1) arbitrary array accessing (random access over an array's entire length) and (2) conditional branching (change control to a different location only if some condition is satisfied).

    Essentially every computer CPU has been Turing-complete, though some computing hardware, like FPGA's, are not, in general, Turing-complete. Most common programming languages are also Turing-complete, though there are some exceptions like HTML.

    It looks as if a resource-limited Turing machine is as far as one can go in physically realizable models of computation.

  2. Top | #2
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Lebanon, OR
    Posts
    5,767
    Archived
    16,829
    Total Posts
    22,596
    Rep Power
    76
    Pushdown automata have an interesting property. Every Context-free grammar can be implemented with a pushdown automaton. A grammar, in this context, is a set of symbols with a set of production rules for them. For a context-free grammar, each production rule replaces a symbol with string of symbols, a string that can contain zero symbols or one symbol. I will use as an example nonnegative integers in decimal notation, using Backus–Naur form.

    <number> ::= 0 | <nonzero-digit> <trailing-digits>
    <trailing-digits> ::= <digit> <trailing-digits> | ""
    <digit> ::= 0 | <nonzero-digit>
    <nonzero-digit> ::= any of 1 to 9

    Natural languages are, in general, not context-free, though some aspects of them can be described with context-free grammars.

Similar Threads

  1. Suicide machines?
    By lpetrich in forum Morals & Principles
    Replies: 64
    Last Post: 02-18-2019, 11:44 PM
  2. Replies: 1
    Last Post: 07-22-2018, 05:43 AM
  3. The Turing Machine
    By steve_bank in forum Mathematics
    Replies: 10
    Last Post: 05-22-2018, 06:51 AM
  4. Limitations of Turing tests
    By Kharakov in forum Other Philosophical Discussions
    Replies: 23
    Last Post: 09-29-2015, 11:46 AM
  5. France latest country to ban use of excessively thin models
    By Axulus in forum Political Discussions
    Replies: 46
    Last Post: 04-09-2015, 03:03 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •