可计算性和复杂性/形式语言/乔姆斯基层次结构/无限制语言
顾名思义，无限制语言类别是乔姆斯基层次结构中最不严格的类别，它是无限制文法生成的语言集合。无限制文法是包含有限数量的规则 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;
}