Figuring out a definition

[ericung]

Figuring out a formal definition for a decider in my terms is a main issue right now.

[ericung]

Turing machine

1. Q is the set of states
2. Sigma is the input alphabet not containing the blank symbol u
3. Tau is the tape alphabet where u is in tau and sigma is in tau
4. Sigma: Q x T => Q x Tau x {L, R} is the transition function
5. q0 is in Q is the start state
6. qaccept is in Q is the accept state
7. qreject is in Q is the reject state where qreject != qaccept

[ericung]

chapter 4 - Rational Expressions

[ericung]

This is a semiring

[ericung]

It defers from a regular definition of a turing machine because it is a state inside a state. however, if we can map the state inside a state to a regular state shown in the book, we have shown that it is equivalent to a turing machine instead of redeveloping a definition to a turing machine.

[ericung]

todo: need to create a mapping function that maps a decider that uses a turing machine.

[ericung]

Rational functions in chapter 6.

K[x] and K[[x]]. S is an element of K[[x]]

S = Sigma{n>=0}a_n*x^n

[ericung]

Multitape Turing machines

[ericung]

Sigma: Q x T^k => Q x T^k x {L,R,S}

[ericung]

Found a suitable definition.