date: 2024-11-07
title: 08-TOC-TM
status: DONE
author:
- AllenYGY
tags:
- NOTE
- TOC
- TuringMachine
publish: True
TOC-Turing Machine
A Turing Machine is a 7-tuple:
A Turing Machine can be described as
Let
Read the input
Ensure that
Zig-zag across the tape to the corresponding positions on either side of
When all symbols to the left of
Problem:
Input: Given a string
Question: Is
Algorithm:
The above example shows the basic features of a Turing Machine.
(Preprocessing) Read the input (over an alphabet
Note: The preprocessing is trivial, tedious, and required by every Turing Machine (TM). Thus, this part of the TM is always omitted.
To cross out symbols, a set of tape symbols
The state machine has a transition function:
And of the output:
Accept
A TM
Reject
A TM
If the transition function is only a partial function (some elements in the domain is undefined),
A TM
Using a partial transition function can omit the reject states.
To make a partial function be total, we just artificially add those undefined transitions to a reject state.
The language for TM are of two types.
A language
We say
A language
We say
When a TM halts on an input,
A TM has a side effect if users need to read tape content to get the desired output. (Using only states of the TM is insufficient to express the output.)
If a TM has no side effect and is only used for checking its output, it is pure; otherwise, it is impure.