可計算性和複雜性/形式語言/喬姆斯基層次結構/無限制語言
顧名思義，無限制語言類別是喬姆斯基層次結構中最不嚴格的類別，它是無限制文法生成的語言集合。無限制文法是包含有限數量的規則 A -> B 的文法，其中 A 和 B 是終結符和非終結符的字串，並且 A 不是空字串。這些文法產生的語言也稱為遞迴可列舉語言，因為理論上一個遞迴函式可以生成它們中的所有字串，儘管不一定在有限的時間內。
等價於無限制語言類別的是被圖靈機識別的語言類別。圖靈機 (TM) 與 LBA 相同（參見 上下文敏感語言），只有一個例外：圖靈機的磁帶是無限的。在標準形式中，圖靈機的磁帶有一個左端點，但向右無限延伸。磁帶的其他無限模型，例如雙向無限的磁帶或多個無限的磁帶，等價於標準形式。
圖靈機是層次結構中最強大的機器，它有能力模擬任何其他機器。它的能力等同於大多數程式語言，儘管計算機只有有限的記憶體，而真正的圖靈機具有無限的記憶體。
圖靈機也可以被程式設計為稱為通用圖靈機 (UTM) 的東西，它是一個可以接受另一個 TM（作為字串編碼）作為輸入的單個 TM（意味著單個狀態集、規則集和字母表），以及一個輸入字串。通用圖靈機然後可以模擬另一個 TM 執行輸入字串。這種對自身類別的通用模擬是層次結構中其他機器都不具有的屬性。其中一些可以被程式設計為模擬其類別的特定子集，但沒有一個可以模擬其類別的任何給定成員。
儘管它們可能很強大，但它們確實有侷限性。最明顯的侷限性之一是，與 LBA 不同，TM 由於無限的磁帶，有無限數量的條件。這意味著 TM 不僅可以迴圈，它還可以處於一個無限執行的非停止模式中，永遠不會迴圈。例如，考慮一個天真地程式設計的 TM，它旨在以一個正整數 *a* 作為輸入，並透過計算它並在磁帶上打印出來來確定 *a* 的平方根是否為有理數。如果該機器被賦予數字 2 作為輸入，它將永遠無法完成列印無理數 ，因此將永遠執行。
以下程式碼是 Perl 中的示例 TM 模擬器。給定機器的描述和一個輸入字串，它模擬機器處理輸入字串，並顯示機器是否接受。
語法是：progname.pl TMFile inputFile，其中 TMFile 是一個包含 TM 指令的文字檔案，inputFile 是一個包含輸入字串的文字檔案。一些示例輸入，包括用於使機器乘以兩個數字的 TM 指令集，可以在 示例 TM 輸入 下找到
Perl 中的示例 TM 模擬器。
#!usr/bin/perl
use Text::ParseWords;
use strict;
use warnings;
# Grabs the filenames for the machine and the word to be run on it.
my $tmFile = $ARGV[0];
my $input = $ARGV[1];
# We use subroutines to parse and verify the data in the input files.
# The machine data is stored in the $machine structure as the keys rules, accepts, alphabet, and startState.
my $machine = readTM($tmFile);
# Rules and accepts are extracted from the $machine structure for ease of access.
my @rules = @{$machine->{rules}};
my %accepts = %{$machine->{accepts}};
# This reads the input file and parses it into an array of strings, with each element being one input symbol.
# It checks to make sure the elements are all in the machine's alphabet.
my @tape = readInput($input, $machine->{alphabet});
# $changed records whether or not a rule has been used when running through the rules list to make transitions.
my $changed = 1;
# $state is the state the Turing Machine is in, and is initialized to the start state from the machine file.
my $state = $machine->{startState};
# $tapeIndex is the position of the machine's head on the tape.
my $tapeIndex = 0;
# Now that the machine is initialized, we can begin making transitions
# As long as things keep changing, keep cycling through the rules.
while($changed)
{
# Unless it changes while going through the rules, the machine will terminate.
$changed = 0;
# The current tape is printed, with the symbol under the head highlighted.
print "@tape[0..$tapeIndex-1]<".$tape[$tapeIndex].">@tape[$tapeIndex+1..$#tape]\n";
# The current state of the machine is printed.
print "$state\n";
# A new state is calculated by checking conditions against the list of rules
for my $ruleRef (@rules)
{
# print "::$ruleRef->[0]??$branches[$i][0]";
# print "::$ruleRef->[1]??$string[$branches[$i][1]]";
# print "::$ruleRef->[2]??".$branches[$i][2][-1]."::\n";
# Checks the current state and tape symbol against the rule being examined
if ($ruleRef->[0] eq $state &&
$ruleRef->[1] eq $tape[$tapeIndex])
{
# The state transition is printed.
# print "State: ".$state." -> ".$ruleRef->[2]."\n\n";
# Set the new state,
$state = $ruleRef->[2];
# Write the new symbol to the tape,
$tape[$tapeIndex] = $ruleRef->[3];
# Shift the tape to the new index,
$tapeIndex += $ruleRef->[4];
# and make sure it hasn't run past the left edge of the tape.
if ($tapeIndex < 0) { $tapeIndex = 0; }
# If the machine nears the end of the allocated tape, expand the tape.
if ($tapeIndex >= $#tape-1) { push(@tape, "_"); }
$changed = 1;
# Once we've made a transition, we can stop and begin looking for the next one.
last;
}
}
}
# When there are no more possible transitions, if the machine is in an accepting state,
if (exists($accepts{$state}))
{
# Print that it accepts and quit.
print "The machine accepts the string.\n";
exit;
}
# Otherwise, print that it does not accept, and quit.
print "The machine does not accept the string.\n";
exit;
###################################################
sub readTM
# This subroutine reads the machine data from the specified file into variables (mostly hashes).
{
my (%states, %accepts, %alphabet, @rules);
open(INFILE, shift) or die "Can't open machine file: $!";
# This block reads the list of states from the machine file.
# Discards the section header,
<INFILE>;
my $line = <INFILE>;
chomp($line);
my @words = parse_line('\s+', 0, $line);
for (@words)
{
# records the state names for checking the rules,
$states{$_} = 0;
}
# This block reads the start state from the machine file.
# Discards the header,
<INFILE>;
my $startState = <INFILE>;
# takes the whole line as the start state,
chomp($startState);
# and makes sure that the start state is defined in the list of states.
exists($states{$startState}) or die "The start state $startState isn't a state!";
# This block reads the list of accepting states from the machine file.
# Discards the header,
<INFILE>;
$line = <INFILE>;
chomp($line);
# breaks up the line into state names,
@words = parse_line('\s+', 0, $line);
for (@words)
{
# checks to make sure that the accept states are defined states,
exists($states{$_}) or die "$_ isn't a state!";
# and defines those names in a new hash. The use of a hash makes it easier to determine later if a specific state name accepts or not.
$accepts{$_} = 1;
}
# This block reads the list of symbols in the alphabet from the machine file.
# Discards the header,
<INFILE>;
$line = <INFILE>;
chomp($line);
# breaks up the line into alphabet symbols (note that the symbols can be of arbitrary length),
@words = parse_line('\s+', 0, $line);
# e is used as the empty symbol in the rules.
$alphabet{e} = 1;
for (@words)
{
# This records which symbols are in the alphabet for checking the rules.
$alphabet{$_} = 0;
}
# This block reads the state transition rules from the machine file.
# Discards the header,
<INFILE>;
# This variable synchronizes the position of each rule in the rules array.
my $rulesCounter=0;
while(<INFILE>)
{
# breaks each rule into start state, input symbol, stack symbol, end state, and new stack symbol.
chomp;
@words = parse_line('\s+', 0, $_);
# checks that the first four pieces are defined in the state and alphabet hashes,
exists($states{$words[0]}) or die "$words[0] isn't a defined state!";
exists($alphabet{$words[1]}) or die "$words[1] isn't defined in the alphabet!";
exists($states{$words[2]}) or die "$words[2] isn't a defined state!";
exists($alphabet{$words[3]}) or die "$words[3] isn't defined in the alphabet!";
# and converts the left/right instruction into a number to be added to the position counter.
if ($words[4] eq "left" || $words[4] eq "-1")
{
$words[4]=-1;
}
elsif ($words[4] eq "right" || $words[4] eq "+1")
{
$words[4]=1;
}
else
{
die "$words[4] isn't left, right, -1, or +1!";
}
# then creates an array of each rule.
for (0..4)
{
$rules[$rulesCounter][$_] = $words[$_];
}
# The synchronization variable has to be updated.
$rulesCounter++;
}
# Reading complete, the subroutine closes the file and returns the name of the start state.
close INFILE;
# The relevant data is stored in the $machine structure and returned to the main routine.
my $machine =
{
rules => \@rules,
accepts => \%accepts,
alphabet => \%alphabet,
startState => $startState
};
return $machine;
}
sub readInput
# This subroutine reads the starting tape from the specified file into an array of symbols.
{
open(INFILE, shift) or die "Can't open ".$input.": $!";
my $alphaRef = shift;
# The first line of the file is read as the initial state of the tape, with symbols delimited by spaces.
my $line = <INFILE>."";
chomp($line);
my @tape = parse_line('\s+', 0, $line);
# This makes sure every symbol in the input string was defined in the machine's alphabet.
for (@tape)
{ exists($alphabet->{$_}) or die "$_ in $input isn't in this machine's alphabet!"; }
close INFILE;
return @tape;
}